Submission #3224923


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 = 4e5+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) if(ans[Q[i].id]==-1) ans[Q[i].id] = l;
		return ;
	}
	int mid = (l + r) >> 1;
	if(cur > mid) init();
	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){1,m,1,Qn};
	init();
	while(front < rear){
		queue tmp = q[front++];
		solve(tmp.l,tmp.r,tmp.L,tmp.R);
	}
}
inline int ran(){
	return rand() << 15 | rand();
}
int main(){
	n = rd();m = rd();
	Rep(i,1,m){
		int a = rd(),b = rd();
		V[i] = (node){a,b};
	}
	Qn = rd();
	mem(ans,-1);
	Rep(i,1,Qn){
		int x = rd(),y = rd(),z = rd();
		Q[i] = (query){x,y,z,i};
		if(z==1||z==2) ans[i]=0;
	}
	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 1000
Code Size 2613 Byte
Status AC
Exec Time 151 ms
Memory 19584 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 1
AC × 33
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 AC 4 ms 12032 KB
1_00.txt AC 69 ms 19584 KB
1_01.txt AC 106 ms 19456 KB
1_02.txt AC 74 ms 19328 KB
1_03.txt AC 111 ms 19456 KB
1_04.txt AC 77 ms 19328 KB
1_05.txt AC 113 ms 19328 KB
1_06.txt AC 78 ms 19200 KB
1_07.txt AC 114 ms 19200 KB
1_08.txt AC 82 ms 19200 KB
1_09.txt AC 119 ms 19200 KB
1_10.txt AC 91 ms 19200 KB
1_11.txt AC 123 ms 19200 KB
1_12.txt AC 103 ms 19200 KB
1_13.txt AC 117 ms 19200 KB
1_14.txt AC 77 ms 19200 KB
1_15.txt AC 85 ms 19200 KB
1_16.txt AC 133 ms 17152 KB
1_17.txt AC 147 ms 17152 KB
1_18.txt AC 146 ms 17152 KB
1_19.txt AC 134 ms 17152 KB
1_20.txt AC 139 ms 17024 KB
1_21.txt AC 138 ms 17152 KB
1_22.txt AC 144 ms 17152 KB
1_23.txt AC 147 ms 17152 KB
1_24.txt AC 151 ms 17024 KB
1_25.txt AC 143 ms 17152 KB
1_26.txt AC 138 ms 17024 KB
1_27.txt AC 143 ms 17152 KB
1_28.txt AC 139 ms 17152 KB
1_29.txt AC 149 ms 17024 KB
1_30.txt AC 145 ms 17152 KB
1_31.txt AC 138 ms 17024 KB