Submission #3224834
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 = 1e5+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++];
if(tmp.l==0) init();
solve(tmp.l,tmp.r,tmp.L,tmp.R);
}
}
int main(){
n = rd();m = rd();
Rep(i,1,m){
int a = rd(),b = rd();
V[i] = (node){a,b};
}
Qn = rd();
Rep(i,1,Qn){
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 6
2 3
4 5
1 2
1 3
1 4
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 |
2483 Byte |
Status |
WA |
Exec Time |
2103 ms |
Memory |
7680 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1000 |
Status |
|
|
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 |
2 ms |
4352 KB |
1_00.txt |
TLE |
2103 ms |
7296 KB |
1_01.txt |
WA |
81 ms |
7040 KB |
1_02.txt |
WA |
68 ms |
7680 KB |
1_03.txt |
WA |
79 ms |
6912 KB |
1_04.txt |
TLE |
2103 ms |
7040 KB |
1_05.txt |
WA |
84 ms |
6912 KB |
1_06.txt |
TLE |
2103 ms |
7040 KB |
1_07.txt |
WA |
83 ms |
6784 KB |
1_08.txt |
TLE |
2103 ms |
6912 KB |
1_09.txt |
WA |
85 ms |
6656 KB |
1_10.txt |
TLE |
2103 ms |
6912 KB |
1_11.txt |
WA |
96 ms |
6912 KB |
1_12.txt |
TLE |
2103 ms |
6912 KB |
1_13.txt |
WA |
113 ms |
7552 KB |
1_14.txt |
AC |
78 ms |
7552 KB |
1_15.txt |
WA |
82 ms |
7552 KB |
1_16.txt |
WA |
78 ms |
6656 KB |
1_17.txt |
WA |
100 ms |
6656 KB |
1_18.txt |
WA |
83 ms |
6656 KB |
1_19.txt |
WA |
120 ms |
6784 KB |
1_20.txt |
WA |
86 ms |
6528 KB |
1_21.txt |
WA |
84 ms |
6656 KB |
1_22.txt |
WA |
77 ms |
6528 KB |
1_23.txt |
WA |
96 ms |
6656 KB |
1_24.txt |
WA |
74 ms |
6528 KB |
1_25.txt |
WA |
74 ms |
6656 KB |
1_26.txt |
WA |
76 ms |
6528 KB |
1_27.txt |
WA |
72 ms |
6656 KB |
1_28.txt |
WA |
72 ms |
6528 KB |
1_29.txt |
WA |
106 ms |
6528 KB |
1_30.txt |
WA |
93 ms |
6656 KB |
1_31.txt |
WA |
76 ms |
6528 KB |