Submission #995844

#TimeUsernameProblemLanguageResultExecution timeMemory
995844cpptowinExperimental Charges (NOI19_charges)C++17
14 / 100
32 ms10316 KiB
#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 100010 #define N 1010 #define fi first #define se second #define pb emplace_back #define en cout << "\n"; #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] = 1e5 + 5; } 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]; if(u == v) { cout << "R";en; continue; } 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 << 'R'; else cout << 'A'; } en; } }

Compilation message (stderr)

charges.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main()
      | ^~~~
charges.cpp: In function 'int main()':
charges.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
charges.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...