Submission #575985

#TimeUsernameProblemLanguageResultExecution timeMemory
575985jiahngInside information (BOI21_servers)C++14
50 / 100
342 ms110156 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; //~ #define ll int #define int ll typedef pair<int32_t, int32_t> pi; typedef vector <int> vi; typedef vector <pi> vpi; typedef pair<pi, ll> pii; typedef set <ll> si; typedef long double ld; #define f first #define s second #define mp make_pair #define FOR(i,s,e) for(int i=s;i<=int(e);++i) #define DEC(i,s,e) for(int i=s;i>=int(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define maxn 120001 #define INF 1e9 #define MOD 1000000007 typedef pair <vi, int> pvi; typedef pair <int,pi> ipi; typedef vector <pii> vpii; int N,K; vpi adj[maxn]; int sz[maxn], lvl[maxn],par[maxn][30]; void find_sz(int x, int p){ sz[x] = 1; aFOR(i,adj[x]) if (i.f != p && lvl[i.f] == -1){ find_sz(i.f,x); sz[x] += sz[i.f]; } } int find_cent(int x,int p, int m){ aFOR(i,adj[x]) if (i.f != p && lvl[i.f] == -1 && sz[i.f] > m / 2) return find_cent(i.f,x,m); return x; } bool inc[maxn][30], _dec[maxn][30]; int fi[maxn][30], la[maxn][30]; // All are measured top-down void find_vals(int x, int p, int d, int incv, int decv, int first_edge, int last_edge){ inc[x][d] = (incv != -1); _dec[x][d] = (decv != -1); fi[x][d] = first_edge; la[x][d] = last_edge; aFOR(i,adj[x]) if (i.f != p && lvl[i.f] == -1){ int nincv, ndecv, nfirst_edge; if (incv == -1 || i.s < incv) nincv = -1; else nincv = i.s; if (decv == -1 || i.s > decv) ndecv = -1; else ndecv = i.s; if (first_edge == -1) nfirst_edge = i.s; else nfirst_edge = first_edge; find_vals(i.f, x, d, nincv, ndecv, nfirst_edge, i.s); } } void decomp(int x,int p,int d){ find_sz(x, -1); int cent = find_cent(x, -1, sz[x]); lvl[cent] = d; //~ cout << p << ' ' << cent << '\n'; par[cent][d] = cent; FOR(i,0,d-1) par[cent][i] = par[p][i]; find_vals(cent, -1, d, 0, N+1, -1, -1); aFOR(i,adj[cent]) if (lvl[i.f] == -1) decomp(i.f,cent, d+1); } char ch; int a,b; int32_t main(){ fast; cin >> N >> K; int co = 1; vector <pii> queries; FOR(i,1,N+K-1){ cin >> ch; if (ch == 'S'){ cin >> a >> b; adj[a].pb(pi(b, co)); adj[b].pb(pi(a,co)); co++; }else if (ch == 'Q'){ cin >> a >> b; queries.pb(pii(pi(a,b), co-1)); }else{ cin >> a; queries.pb(pii(pi(a, -1), co-1)); } } mem(lvl, -1); mem(par, -1); decomp(1,-1,0); aFOR(i,queries){ if (i.f.s != -1){ int x = i.f.s, y = i.f.f; if (x == y){ cout << "yes\n"; continue; } int lca = 0; DEC(d,29,0) if (par[x][d] != -1 && par[x][d] == par[y][d]){ lca = d; break; } //~ cout << lca << ' '; if (_dec[x][lca] && inc[y][lca]){ if (fi[x][lca] == -1 || fi[y][lca] == -1 || fi[x][lca] < fi[y][lca]){ int last = la[y][lca];; if (lvl[y] == lca) last = fi[x][lca]; if (last <= i.s){ cout << "yes\n"; continue; } } } cout << "no\n"; } } }
#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...
#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...