2594: [Wc2006]水管局长数据加强版

2594: [Wc2006]水管局长数据加强版

Time Limit: 25 Sec   Memory Limit: 128 MB Submit: 2556   Solved: 817 [ Submit][ Status][ Discuss]

Description

SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。 在处理每项送水任务之前，路径上的水管都要进行一系列的准备操作，如清洗、消毒等等。嘟嘟在控制中心一声令下，这些水管的准备操作同时开始，但由于各条管道的长度、内径不同，进行准备操作需要的时间可能不同。供水公司总是希望嘟嘟能找到这样一条送水路径，路径上的所有管道全都准备就绪所需要的时间尽量短。嘟嘟希望你能帮助他完成这样的一个选择路径的系统，以满足供水公司的要求。另外，由于MY市的水管年代久远，一些水管会不时出现故障导致不能使用，你的程序必须考虑到这一点。 不妨将MY市的水管网络看作一幅简单无向图（即没有自环或重边）：水管是图中的边，水管的连接处为图中的结点。  

Input

输入文件第一行为3个整数：N, M, Q分别表示管道连接处（结点）的数目、目前水管（无向边）的数目，以及你的程序需要处理的任务数目（包括寻找一条满足要求的路径和接受某条水管坏掉的事实）。 以下M行，每行3个整数x, y和t，描述一条对应的水管。x和y表示水管两端结点的编号，t表示准备送水所需要的时间。我们不妨为结点从1至N编号，这样所有的x和y都在范围[1, N]内。 以下Q行，每行描述一项任务。其中第一个整数为k：若k=1则后跟两个整数A和B，表示你需要为供水公司寻找一条满足要求的从A到B的水管路径；若k=2，则后跟两个整数x和y，表示直接连接x和y的水管宣布报废（保证合法，即在此之前直接连接x和y尚未报废的水管一定存在）。  

Output

按顺序对应输入文件中每一项k=1的任务，你需要输出一个数字和一个回车/换行符。该数字表示：你寻找到的水管路径中所有管道全都完成准备工作所需要的时间（当然要求最短）。  

Sample Input

4 4 3 1 2 2 2 3 3 3 4 2 1 4 2 1 1 4 2 1 4 1 1 4

Sample Output

2 3 【原题数据范围】 N ≤ 1000 M ≤ 100000 Q ≤ 100000 测试数据中宣布报废的水管不超过5000条；且任何时候我们考虑的水管网络都是连通的，即从任一结点A必有至少一条水管路径通往任一结点B。 【加强版数据范围】 N ≤ 100000 M ≤ 1000000 Q ≤ 100000 任何时候我们考虑的水管网络都是连通的，即从任一结点A必有至少一条水管路径通往任一结点B。 【C/C++选手注意事项】 由于此题输入规模较大（最大的测试点约20MB），因此即使使用scanf读入数据也会花费较多的时间。为了节省读入耗时，建议使用以下函数读入正整数（返回值为输入文件中下一个正整数）： int getint() { char ch = getchar(); for ( ; ch > '9' || ch < '0'; ch = getchar()); int tmp = 0; for ( ; '0' <= ch && ch <= '9'; ch = getchar()) tmp = tmp * 10 + int(ch) - 48; return tmp; }

HINT

Source

鸣谢Kac

[ Submit][ Status][ Discuss] 数据加强？？ 我们把操作倒过来看看？？ 于是删边操作等价于加边 问题变成，，不断加边与询问(x,y)路径上权值最大的边，还是一样，，边也看成点来搞splay 于是这题就完啦！！ 完了？？？ 我TM，，，T了一个早上，，，一个早上，，，读入输出优化都上了，还是没用。。GG 实际上，，splay拥有巨大的常数~如果m条边，每条都去检验下，，GG 所以一开始用kruskal算法来配合加边操作，立刻跑得飞起~ #include<iostream> #include<cstdio> #include<queue> #include<vector> #include<bitset> #include<algorithm> #include<cstring> #include<map> #include<stack> #include<set> #include<cmath> #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int maxn = 1E5 + 10; const int maxm = 11*maxn; const int INF = ~0U>>1; const int mo = 10000007; struct E{ int x,y,t,id; E(int _x = 0,int _y = 0,int _t = 0) {x = _x; y = _y; t = _t;} bool operator < (const E &b) const { if (x < b.x) return 1; if (x > b.x) return 0; return y < b.y; } }edgs[maxn*10],e[maxn*10]; int n,m,tot,q,ch[maxm][2],rev[maxm],fa[maxm],ans[maxn],typ[maxn],s[maxn*2], Fa[maxn],A[maxn],B[maxn],key[maxm],pfa[maxm],Max[maxm],pos[maxm]; bool not_use[maxn*10]; bool cmp(const E &a,const E &b) {return a.t < b.t;} void maintain(int x) { Max[x] = key[x]; pos[x] = x; if (ch[x][0] && Max[ch[x][0]] > Max[x]) Max[x] = Max[ch[x][0]],pos[x] = pos[ch[x][0]]; if (ch[x][1] && Max[ch[x][1]] > Max[x]) Max[x] = Max[ch[x][1]],pos[x] = pos[ch[x][1]]; } void rotate(int x) { int y = fa[x],z = fa[y]; pfa[x] = pfa[y]; pfa[y] = 0; int d = ch[y][1] == x?1:0; ch[y][d] = ch[x][d^1]; if (ch[y][d]) fa[ch[y][d]] = y; maintain(y); ch[x][d^1] = y; fa[y] = x; fa[x] = z; maintain(x); if (z) ch[z][ch[z][1] == y] = x,maintain(z); } void pushdown(int x) { if (rev[x]) { swap(ch[x][0],ch[x][1]); rev[x] ^= 1; if (ch[x][0]) rev[ch[x][0]] ^= 1; if (ch[x][1]) rev[ch[x][1]] ^= 1; } } void splay(int x) { int top = 0; for (int now = x; now; now = fa[now]) s[++top] = now; while (top) {pushdown(s[top--]);} for (int y; y = fa[x]; rotate(x)) if (fa[y]) rotate((ch[fa[y]][0] == y)^(ch[y][0] == x)?y:x); } int getint() { char ch = getchar(); int ret = 0; while (ch < '0' || '9' < ch) ch = getchar(); while ('0' <= ch && ch <= '9') ret = ret*10 + ch - '0',ch = getchar(); return ret; } void Access(int x) { for (int u = x,v = 0; u; v = u,u = pfa[u]) { splay(u); if (ch[u][1]) fa[ch[u][1]] = 0,pfa[ch[u][1]] = u; if (v) pfa[v] = 0,fa[v] = u; ch[u][1] = v; maintain(u); } } void ChangeRoot(int x) {Access(x); splay(x); rev[x] ^= 1;} void Join(int x,int y) {ChangeRoot(x); pfa[x] = y;} void Cut(int x,int y) {ChangeRoot(x); Access(y); splay(y); fa[x] = ch[y][0] = 0; maintain(y);} int Find_Root(int x) { Access(x); splay(x); while (ch[x][0]) x = ch[x][0]; splay(x); return x; } void Add(int k) { int x = edgs[k].x,y = edgs[k].y; int fx = Find_Root(x); int fy = Find_Root(y); if (fx != fy) { Join(x,n+k); Join(n+k,y); return; } ChangeRoot(x); Access(y); splay(y); if (Max[ch[y][0]] <= edgs[k].t) return; int cut = pos[ch[y][0]]; Cut(edgs[cut-n].x,cut); Cut(cut,edgs[cut-n].y); Join(x,n+k); Join(n+k,y); } int Query(int k) { ChangeRoot(A[k]); Access(B[k]); splay(B[k]); return Max[B[k]]; } int num; char c[20]; void print( int k ) { num = 0; while( k > 0 ) c[++num] = k % 10, k /= 10; while( num ) putchar( c[num--]+48 ); putchar( 10 ); } int Search(int k,int l,int r) { if (l == r) return l; int mid = (l + r) >> 1; if (edgs[mid].x == A[k] && edgs[mid].y == B[k]) return mid; if (edgs[mid].x < A[k]) return Search(k,mid+1,r); if (edgs[mid].x > A[k]) return Search(k,l,mid); if (edgs[mid].y < B[k]) return Search(k,mid+1,r); return Search(k,l,mid); } int father(int x) {return x == Fa[x]?x:Fa[x] = father(Fa[x]);} void Add2(int k) {Join(edgs[k].x,n+k); Join(n+k,edgs[k].y);} void kruskal() { for (int i = 1; i <= n; i++) Fa[i] = i; for (int i = 1; i <= m; i++) e[i] = edgs[i],e[i].id = i; sort(e + 1,e + m + 1,cmp); for (int i = 1; i <= m; i++) if (!not_use[e[i].id]) { int fx = father(e[i].x); int fy = father(e[i].y); if (fx != fy) { Fa[fx] = fy; Add2(e[i].id); } } } int main() { #ifdef DMC freopen("tube7.in","r",stdin); freopen("test.txt","w",stdout); #endif n = getint(); m = getint(); q = getint(); for (int i = 1; i <= m; i++) { int x = getint(),y = getint(),t = getint(); if (x > y) swap(x,y); edgs[i] = E(x,y,t); } sort(edgs + 1,edgs + m + 1); for (int i = 1; i <= n; i++) Max[i] = key[i] = -INF; for (int i = n + 1; i <= n + m; i++) Max[i] = key[i] = edgs[i-n].t; for (int i = 1; i <= q; i++) { typ[i] = getint(); A[i] = getint(); B[i] = getint(); if (A[i] > B[i]) swap(A[i],B[i]); if (typ[i] == 2) { A[i] = Search(i,1,m); not_use[A[i]] = 1; } } kruskal(); for (int i = q; i; i--) if (typ[i] == 1) ans[i] = Query(i); else Add(A[i]); for (int i = 1; i <= q; i++) if (typ[i] == 1) print(ans[i]); return 0; }