Submission #3224863


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define mem(x,v) memset(x,v,sizeof(x))
#define gc getchar
#define pc putchar
#define fi first
#define queue QQQ
#define se second
#define debug(x) cout << #x" = " << x << endl;
#define pp(x,y) cout << "pp: " << x << " " << y << endl;
#define rank __RANK
inline ll read(){
	register ll x=0,f=1;register char c=gc();
	for(;!isdigit(c);c=gc())if(c=='-')f=-1;
	for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}
#define rd read
void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
void writeln(ll x){write(x);puts("");}
const int maxn = 2e5+233;
struct node{
	int a,b;
}V[maxn];
struct query{
	int a,b,v,id;
}Q[maxn],tmp[maxn];
struct queue{
	int l,r,L,R;
}q[maxn];int front,rear;
int fa[maxn],n,m,Qn,cur,size[maxn];
inline int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void init(){
	Rep(i,1,n) fa[i] = i,size[i] = 1;
	cur = 0;
}
void merge(int x,int y){
	if(find(x)==find(y)) return ;
	size[find(y)] += size[find(x)];
	fa[find(x)] = find(y);
}
int ans[maxn];
inline int calc(int x,int y){
	if(find(x) == find(y)) return size[find(x)];
	else return size[find(x)] + size[find(y)];
}
void solve(int l,int r,int L,int R){
	if(l==r){
		Rep(i,L,R) ans[Q[i].id] = l;
		return ;
	}
	int mid = (l + r) >> 1;
	while(cur+1 <= mid){
		++cur;
		merge(V[cur].a,V[cur].b);
	}
	Rep(i,L,R) tmp[i] = Q[i];
	int LL = L,RR = R;
	Rep(i,L,R){
		int x = tmp[i].a,y = tmp[i].b,z = tmp[i].v;
		if(calc(x,y) >= z) Q[LL++] = tmp[i];//mid是可以满足条件的 
												else Q[RR--] = tmp[i]; 
	}
	if(L<=LL-1)q[rear++] = (queue){l,mid,L,LL-1};
	if(RR+1<=R)q[rear++] = (queue){mid+1,r,RR+1,R};
}
void Main(){
	front = rear = 0;
	q[rear++] = (queue){0,m,1,Qn};
	while(front < rear){
		queue tmp = q[front++];
//		printf("[%d %d]\n",front,rear);
		if(tmp.l==0) init();
		solve(tmp.l,tmp.r,tmp.L,tmp.R);
	}
}
inline int ran(){
	return rand() << 15 | rand();
}
int main(){
	n = rd();m = rd();
//	n = 1e5,m = 1e5-1;
	Rep(i,1,m){
		int a = rd(),b = rd();
//		int a = i+1,b = ran() % i + 1;
		V[i] = (node){a,b};
	}
	Qn = rd();
	Qn = 1e5;
	Rep(i,1,Qn){
//		int x = ran()%n+1,y = ran()%n+1,z = ran() % n + 1;
		int x = rd(),y = rd(),z = rd();
		Q[i] = (query){x,y,z,i};
	}
	Main();
	Rep(i,1,Qn) writeln(ans[i]);
	return 0;
}
/*
5 7
2 3
2 5 
1 2
1 3
1 4
3 5 
1 5
6
2 4 1
2 4 2
2 4 3
1 3 4
1 3 5
1 3 6
*/

Submission Info

Submission Time
Task D - Stamp Rally
User wzporz
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2708 Byte
Status WA
Exec Time 2103 ms
Memory 12928 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
TLE × 1
AC × 3
WA × 29
TLE × 1
Set Name Test Cases
Sample 0_00.txt
All 0_00.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt
Case Name Status Exec Time Memory
0_00.txt TLE 2103 ms 4352 KB
1_00.txt WA 67 ms 12928 KB
1_01.txt WA 83 ms 12800 KB
1_02.txt WA 69 ms 12672 KB
1_03.txt WA 81 ms 12672 KB
1_04.txt WA 78 ms 12672 KB
1_05.txt WA 85 ms 12672 KB
1_06.txt WA 75 ms 12544 KB
1_07.txt WA 83 ms 12544 KB
1_08.txt WA 80 ms 12416 KB
1_09.txt WA 89 ms 12544 KB
1_10.txt AC 90 ms 12416 KB
1_11.txt WA 98 ms 12544 KB
1_12.txt AC 103 ms 12416 KB
1_13.txt WA 114 ms 12544 KB
1_14.txt AC 81 ms 12544 KB
1_15.txt WA 84 ms 12544 KB
1_16.txt WA 78 ms 12416 KB
1_17.txt WA 103 ms 12416 KB
1_18.txt WA 86 ms 12416 KB
1_19.txt WA 122 ms 12544 KB
1_20.txt WA 87 ms 12416 KB
1_21.txt WA 84 ms 12416 KB
1_22.txt WA 79 ms 12416 KB
1_23.txt WA 97 ms 12416 KB
1_24.txt WA 76 ms 12416 KB
1_25.txt WA 77 ms 12416 KB
1_26.txt WA 77 ms 12416 KB
1_27.txt WA 75 ms 12416 KB
1_28.txt WA 73 ms 12416 KB
1_29.txt WA 110 ms 12416 KB
1_30.txt WA 96 ms 12416 KB
1_31.txt WA 77 ms 12416 KB