Submission #935657

#TimeUsernameProblemLanguageResultExecution timeMemory
935657berrInside information (BOI21_servers)C++17
50 / 100
370 ms125460 KiB
#include <bits/stdc++.h> using namespace std; #define int long long struct val{ int n, cnt = 0; vector<vector<array<int, 2>>> g; vector<array<int, 18>> vu, vd, p; vector<array<int, 18>> ma, mi; vector<int> ti, to; vector<int> d; val(){}; val(vector<vector<array<int, 2>>> _g){ n = _g.size(); g = _g; d.resize(n, -1); vu.resize(n); vd.resize(n); p.resize(n); ti.resize(n); to.resize(n); ma.resize(n); mi.resize(n); dfs(0, 0); for(int i=1; i<18; i++){ for(int l=0; l<n; l++){ p[l][i] = p[p[l][i-1]][i-1]; } } for(int i=1; i<18; i++){ for(int l=0; l<n; l++){ ma[l][i]=max(ma[l][i-1], ma[p[l][i-1]][i-1]); mi[l][i]=min(mi[l][i-1], mi[p[l][i-1]][i-1]); if(mi[l][i-1]>=ma[p[l][i-1]][i-1]&&vu[p[l][i-1]][i-1]!=1e18) vu[l][i] = vu[l][i-1]; else vu[l][i] = 1e18; if(ma[l][i-1]<=mi[p[l][i-1]][i-1]&&vd[p[l][i-1]][i-1]!=1e18) vd[l][i] =vd[l][i-1]; else vd[l][i] = 1e18; } } } void dfs(int v, int par){ d[v] = d[par] +1; p[v][0]=par; ti[v] = cnt++; for(auto [i, j]: g[v]){ if(i == par) continue; vu[i][0] = j; vd[i][0]=j; ma[i][0]=j; mi[i][0]=j; dfs(i, v); } to[v] = cnt++; } auto ia(int a, int b){ return ti[a]<=ti[b] && to[a]>= to[b]; } int operator()(int x, int y){ if(x==y)return 0; // 1e18 if no way // max value of that path if(ia(x, y)){ int m = 0, lasty; int tmpy=y; for(int j=17; j>=0; j--){ if((1<<j) <= d[y] && d[y]-(1<<j)>=d[x]){ if(vd[y][j]==1e18) m = 1e18; lasty = ma[y][j]; m = max(m, ma[y][j]); y = p[y][j]; if(lasty>vu[y][0]&&y!=x) m = 1e18; } } if(m==1e18) return 1e18; else return m; } int m = vu[x][0]; int tmp =m; int lastx = m, lasty=vu[y][0]; for(int j=17; j>=0; j--){ if((1<<j) <= d[x] && !ia(p[x][j], y)){ m = max(m, vu[x][j]); lastx = mi[x][j]; x = p[x][j]; if(lastx<vu[x][0]) m = 1e18; } if((1<<j) <= d[y] && !ia(p[y][j], x)){ m = max(m, vd[y][j]); lasty = ma[y][j]; y = p[y][j]; if(lasty>vu[y][0]) m = 1e18; } } if(m != tmp) return 1e18; if(!ia(x, y)&&(!ia(y, x))){ if(vu[x][0]<vu[y][0]) return 1e18; } return m; } }; val a; /* struct centroid{ };*/ signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<vector<array<int, 2>>> g(n); /// a dan b ye erişirkenki max değer /// a dan b ye erişim var mı int time = 1; vector<array<int, 4>> qu; for(int i=1; i<n+k; i++){ char t; cin >> t; if (t=='S'){ time++; int a, b; cin >> a >> b; a--; b--; g[a].push_back({b, time}); g[b].push_back({a, time}); } else if(t=='Q'){ int a, b; cin >> a >> b; a--; b--; // can i go from b to a qu.push_back({0, a, b, time}); } else{ int a; cin >> a; a--; qu.push_back({1, a, a, time}); } } a = val(g); for(auto [i, j, k, l]: qu){ if(i==0){ if(a(j, k)<=l) cout<<"yes\n"; else cout<<"no\n"; } } // centroid c(g); }

Compilation message (stderr)

servers.cpp: In member function 'long long int val::operator()(long long int, long long int)':
servers.cpp:71:17: warning: unused variable 'tmpy' [-Wunused-variable]
   71 |             int tmpy=y;
      |                 ^~~~
#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...