#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
struct DSU
{
vi par,sz,t;
DSU(int n) : par(n),sz(n),t(n) {};
void make(int u)
{
par[u] = u;
sz[u] = 1;
t[u] = inf;
}
int find(int u,int ti)
{
if(t[u] > ti) return u;
return find(par[u],ti);
}
void Union(int u,int v,int ti)
{
u = find(u,ti);
v = find(v,ti);
if(u == v) return ;
if(sz[u] < sz[v]) swap(u,v);
sz[u] += sz[v];
par[v] = u;
minimize(t[v],ti);
}
};
int n,q;
array<int,3> qry[maxn];
vii ke[maxn];
int val[maxn];
void dfs(int u,int par = 0)
{
for(auto [v,w] : ke[u]) if(v != par and val[v] != -1)
{
if(w == 1) val[v] = val[u];
else val[v] = 1 - val[u];
dfs(v,u);
}
}
main()
{
#define name "TASK"
if (fopen(name ".inp", "r"))
{
freopen(name ".inp", "r", stdin);
freopen(name ".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
DSU g(n + 5);
fo(i,1,n) g.make(i);
fo(i,1,q)
{
char t;
cin >> t >> qry[i][1] >> qry[i][2];
if(t != 'Q') qry[i][0] = 1;
else qry[i][0] = 2;
if(qry[i][0] != 2)
{
int val = qry[i][0] == 'A' ? 1 : -1;
ke[qry[i][1]].pb(qry[i][2],val);
ke[qry[i][2]].pb(qry[i][1],val);
g.Union(qry[i][1],qry[i][2],i);
}
}
memset(val,-1,sizeof val);
fo(i,1,n) if(val[i] == -1) val[i] = 0,dfs(i);
fo(i,1,q) if(qry[i][0] == 2)
{
auto [_,u,v] = qry[i];
int l = 1,r = q,res = q + 1;
while(l <= r)
{
int mid = (l + r) >> 1;
if(g.find(u,mid) == g.find(v,mid)) res = mid,r = mid - 1;
else l = mid + 1;
}
if(res > i) cout << '?';
else
{
if(val[u] == val[v]) cout << 'A';
else cout << 'R';
}
en;
}
}
Compilation message
charges.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
81 | main()
| ^~~~
charges.cpp: In function 'int main()':
charges.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | freopen(name ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
charges.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | freopen(name ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
33372 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
33372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1025 ms |
41156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
42324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1035 ms |
42068 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
33372 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
33372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
33372 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
33372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
