# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
256086 |
2020-08-02T09:40:10 Z |
반딧불(#5032) |
Joker (BOI20_joker) |
C++17 |
|
62 ms |
4144 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
int n, m, q;
int l, r;
int edgeX[200002], edgeY[200002];
int chk[200002];
int minNeeded[2002];
pair<int, bool> par[200002];
int sz[200002];
bool parCng[200002], szCng[200002];
stack<pair<int, pair<int, bool> > > parRev;
stack<pair<int, int> > szRev;
pair<int, int> find(int x){
if(x == par[x].first) return par[x];
bool tmp = par[x].second;
if(!parCng[x]) parRev.push(make_pair(x, par[x])), parCng[x] = 1;
par[x] = find(par[x].first);
par[x].second ^= tmp;
return par[x];
}
bool merge(int x, int y){
pair<int, int> px = find(x), py = find(y);
if(px.first == py.first && px.second == py.second) return false;
if(px.first == py.first) return true;
int xx = par[x].second, yy = par[y].second;
x = par[x].first, y = par[y].first;
if(sz[x] < sz[y]) swap(x, y);
if(!parCng[y]) parRev.push(make_pair(y, par[y])), parCng[y] = 1;
par[y] = make_pair(x, xx ^ yy ^ 1);
if(!szCng[x]) szRev.push(make_pair(x, sz[x])), szCng[x] = 1;
if(sz[x] == sz[y]) sz[x]++;
return true;
}
void calculate(int l, int r, int s, int e){
if(l>r) return;
if(l == 1e9){
for(int i=l; i<=r; i++) minNeeded[i] = 1e9;
return;
}
int val = s-1;
int m = (l+r)>>1;
for(int j=l; j<m; j++){
int x1 = edgeX[j];
int x2 = edgeY[j];
if(!merge(x1, x2)){
val = 1e9;
break;
}
}
for(int j=e; j>s; j--){
int x1 = edgeX[j];
int x2 = edgeY[j];
if(!merge(x1, x2)){
val = j-1;
break;
}
}
minNeeded[m] = val;
if(l==r) return;
while(!parRev.empty()){
auto tmp = parRev.top();
par[tmp.first] = tmp.second;
parCng[tmp.first] = 0;
parRev.pop();
}
while(!szRev.empty()){
auto tmp = szRev.top();
sz[tmp.first] = tmp.second;
szCng[tmp.first] = 0;
szRev.pop();
}
calculate(l, m-1, s, val);
calculate(m+1, r, val, e);
}
int main(){
scanf("%d %d %d", &n, &m, &q);
for(int i=1; i<=m; i++){
int s, e;
scanf("%d %d", &s, &e);
edgeX[i] = s, edgeY[i] = e;
}
calculate(1, m, 1, m);
while(q--){
scanf("%d %d", &l, &r);
printf("%s\n", minNeeded[l] >= r ? "YES" : "NO");
}
}
Compilation message
Joker.cpp: In function 'int main()':
Joker.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &s, &e);
~~~~~^~~~~~~~~~~~~~~~~
Joker.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &l, &r);
~~~~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Runtime error |
62 ms |
4144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |