# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
765300 |
2023-06-24T10:33:40 Z |
canadavid1 |
Joker (BOI20_joker) |
C++14 |
|
2000 ms |
9248 KB |
#include <bits/stdc++.h>
using namespace std;
vector<bool> diff;
vector<int> p;
vector<int> siz;
vector<pair<int,int>> history;
vector<bool> legal = {1};
pair<int,bool> find(int a,bool len=0)
{
if (p[a] == -1) return {a,len};
return find(p[a],len^diff[a]); // no path compression
}
bool unite(int a,int b) // true if works, false elsewise
{
auto av = find(a);
auto bv = find(b);
if (av.first == bv.first)
{
history.push_back({-1,-1});
legal.push_back(legal.back()&(av.second!=bv.second));
return legal.back();
}
if (siz[av.first] > siz[bv.first]) swap(av,bv);
// b > a
p[av.first] = bv.first;
siz[bv.first] += siz[av.first];
if (av.second == bv.second) diff[av.first] = true;
history.push_back({av.second,bv.second});
legal.push_back(legal.back());
return legal.back();
}
bool undo()
{
auto ab = history.back(); history.pop_back();
legal.pop_back();
if (ab.first == -1) return legal.back();
p[ab.first] = -1;
diff[ab.first] = false;
siz[ab.second] -= siz[ab.first];
return legal.back();
}
inline bool works()
{
return legal.back();
}
vector<pair<int,int>> edge;
inline void addEdge(int idx)
{
unite(edge[idx].first,edge[idx].second);
}
vector<pair<int,pair<int,int>>> query;
vector<bool> queryvalid;
int N,M,Q,added;
int main()
{
cin >> N >> M >> Q;
diff.assign(N+1,false);
p.assign(N+1,-1);
siz.assign(N+1,1);
queryvalid.assign(Q,false);
edge.push_back({0,0});
for(int i = 0; i < M; i++)
{
int l,r;
cin >> l >> r;
edge.push_back({l,r});
}
for(int i = 0; i < Q; i++)
{
int l,r;
cin >> l >> r;
query.push_back({i,{l,r}});
}
const int TOP = M;
sort(query.begin(),query.end(),[](auto a, auto b){return a.second.second > b.second.second;});
for(int i = M; i > TOP; i--) addEdge(i);
while(query.size() && query.back().second.second <= TOP)
{
for(int i = TOP; i > query.back().second.second; i--) addEdge(i);
for(int i = 1; i < query.back().second.first; i--) addEdge(i);
queryvalid[query.back().first] = works();
for(int i = 1; i < query.back().second.first; i--) undo();
for(int i = TOP; i > query.back().second.second; i--) undo();
query.pop_back();
}
for(int i = M; i > TOP; i--) undo();
for (auto &&i : queryvalid)
{
cout << (i ? "NO\n" : "YES\n");
}
/*
vector<vector<int>> neigh(N+1);
vector<pair<int,int>> edge;
for(int i = 0; i < N; i++)
{
int u,v;
cin >> u >> v;
neigh[u].push_back(v);
neigh[v].push_back(u);
edge.push_back({u,v});
}
vector<pair<int,int>> query(Q);
int l;
for (auto &&r : query) cin >> l >> r.first;
for(int i = 0; i < Q; i++) query[i].second = i;
sort(query.begin(),query.end());
vector<bool> result;
int s;
while(query.size())
{
}*/
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Runtime error |
1 ms |
304 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Runtime error |
1 ms |
304 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Execution timed out |
2035 ms |
9248 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Runtime error |
1 ms |
304 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Runtime error |
1 ms |
304 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Runtime error |
1 ms |
304 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |