| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 905238 |
2024-01-12T20:46:59 Z |
starchan |
Joker (BOI20_joker) |
C++17 |
|
2000 ms |
195160 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)2e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
vector<int> pa(MX, -1);
vector<int> d(MX, 0);
bool works = true;
stack<in> roll;
in leader(int u)
{
if(pa[u] < 0)
return {u, 0};
else
{
auto [v, x] = leader(pa[u]);
return {v, x^d[u]};
}
}
void undo()
{
auto [v, w] = roll.top();
roll.pop();
if(w == 0)
{
works = v;
return;
}
pa[v] = w;
d[v] = 0;
return;
}
void merge(int u, int v)
{
auto [x, dx] = leader(u);
auto [y, dy] = leader(v);
if(x == y)
{
if(dx^dy^1)
{
roll.push({works, false});
works = false;
}
return;
}
if(pa[x] < pa[y])
swap(x, y);//x has fewer elements now.
roll.push({x, pa[x]});
roll.push({y, pa[y]});
pa[y]+=pa[x];
pa[x] = y;
d[x] = dx^dy^1;
return;
}
//kk bipartite dsu (w rollback) ready.
vector<in> edges;
void add(int i)
{
merge(edges[i].f, edges[i].s);
}
vector<int> opt;//opt[i] is smallest thing such that 1, 2, .., i-1, opt[i]+1, ..., n is bipartite.
void dnc(int l, int r, int L, int R)//the DSU currently contains 1, 2, 3, .., l-1 and R+1, R+2, .., n
{
if(l > r)
return;
int m = (l+r)/2;
int SZ = roll.size();
for(int i = l; i < m; i++)
add(i);
opt[m] = R;
while(works && (opt[m] >= (m-1)))
{
add(opt[m]);
opt[m]--;
}
opt[m]++;
while(roll.size() > SZ)
undo();
for(int i = R; i > opt[m]; i--)
add(i);
dnc(l, m-1, L, opt[m]);
while(roll.size() > SZ)
undo();
for(int i = l; i <= m; i++)
add(i);
dnc(m+1, r, opt[m], R);
while(roll.size() > SZ)
undo();
return;
}
signed main()
{
fast();
int t;
cin >> t;
while(t--)
{
int n, m, q;
cin >> n >> m >> q;
edges.resize(m+1);
opt.resize(m+1);
for(int i = 1; i <= m; i++)
cin >> edges[i].f >> edges[i].s;
int rr = INF;
for(int i = 1; i <= m; i++)
{
add(i);
if(works)
continue;
opt[i] = INF;
rr = min(rr, i+1);
}
while(roll.size())
undo();
dnc(1, min(rr-1, m), 1, m);
while(q--)
{
int l, r;
cin >> l >> r;
bool tt = (l < rr)&&(r>=opt[l]);
cout << (tt? "NO\n" : "YES\n");
}
}
return 0;
}
Compilation message
Joker.cpp: In function 'void dnc(long long int, long long int, long long int, long long int)':
Joker.cpp:91:20: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
91 | while(roll.size() > SZ)
| ~~~~~~~~~~~~^~~~
Joker.cpp:96:20: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
96 | while(roll.size() > SZ)
| ~~~~~~~~~~~~^~~~
Joker.cpp:101:20: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
101 | while(roll.size() > SZ)
| ~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
195160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
195160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
195160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
195160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
195160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
195160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
