제출 #416981

#제출 시각아이디문제언어결과실행 시간메모리
416981aryan12Inside information (BOI21_servers)C++17
52.50 / 100
419 ms83764 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 120005; vector<pair<int, int> > g[N]; int cnt = 0; int DP[20][N], isDecreasing[20][N], isIncreasing[20][N]; int depth[N]; void dfs(int node, int par) { //cout << "node = " << node << "\n"; DP[0][node] = par; for(int i = 0; i < g[node].size(); i++) { if(g[node][i].first != par) { isDecreasing[0][g[node][i].first] = g[node][i].second; isIncreasing[0][g[node][i].first] = g[node][i].second; depth[g[node][i].first] = depth[node] + 1; dfs(g[node][i].first, node); } } } int LCA(int x, int y) { if(depth[x] < depth[y]) { swap(x, y); } int diff = depth[x] - depth[y]; for(int i = 19; i >= 0; i--) { if(diff >= (1 << i)) { diff -= (1 << i); x = DP[i][x]; } } if(x == y) return x; for(int i = 19; i >= 0; i--) { if(DP[i][x] != DP[i][y]) { x = DP[i][x]; y = DP[i][y]; } } return DP[0][x]; } bool Satisfied(int a, int b, int cnt) { int lca = LCA(a, b); int diff = depth[b] - depth[lca]; int maxval = -1; int lastvalhere = -1; int prevval = -1; for(int i = 19; i >= 0; i--) { if(diff >= (1 << i)) { diff -= (1 << i); if(isIncreasing[i][b] == -1 || isIncreasing[0][b] <= prevval) { return false; } maxval = max(maxval, isIncreasing[i][b]); lastvalhere = max(lastvalhere, isIncreasing[i][b]); prevval = isIncreasing[i][b]; b = DP[i][b]; } } diff = depth[a] - depth[b]; if(diff != 0) { maxval = max(maxval, isDecreasing[0][a]); } //cout << "lastvalhere = " << lastvalhere << "\n"; prevval = INT_MAX; for(int i = 19; i >= 0; i--) { if(diff >= (1 << i)) { diff -= (1 << i); if(isDecreasing[i][a] == -1 || isDecreasing[0][a] >= prevval) { return false; } if(diff == 0) { if(lastvalhere >= isDecreasing[i][a]) { return false; } } prevval = isDecreasing[i][a]; a = DP[i][a]; } } //cout << "cnt = " << cnt << ", maxval = " << maxval << "\n"; if(maxval > cnt) return false; return true; } int dfs2(int node, int par, int curVal, int cur) { int ans = 1; for(int i = 0; i < g[node].size(); i++) { if(g[node][i].first != par) { if(g[node][i].second <= curVal || g[node][i].second > cur) { continue; } else { ans += dfs2(g[node][i].first, node, g[node][i].second, cur); } } } return ans; } void Solve() { int n, q; cin >> n >> q; q += (n - 1); vector<pair<char, pair<int, int> > > queries; while(q--) { char c; cin >> c; int a, b; if(c == 'S') { cin >> a >> b; g[a].push_back({b, ++cnt}); g[b].push_back({a, cnt}); } else if(c == 'Q') { cin >> a >> b; } else { cin >> a; b = -1; } queries.push_back({c, {a, b}}); } depth[1] = 0; g[1].push_back({-1, 0}); isIncreasing[0][1] = -1; isDecreasing[0][1] = -1; dfs(1, -1); for(int i = 1; i < 20; i++) { for(int j = 1; j <= n; j++) { if(DP[i - 1][j] == -1) { DP[i][j] = -1; } else { DP[i][j] = DP[i - 1][DP[i - 1][j]]; } if(DP[i][j] == -1) { isDecreasing[i][j] = -1; isIncreasing[i][j] = -1; } else { if(isDecreasing[i - 1][j] == -1 || isDecreasing[i - 1][DP[i - 1][j]] == -1) { isDecreasing[i][j] = -1; } else if(isDecreasing[i - 1][j] <= isDecreasing[0][DP[i - 1][j]]) { isDecreasing[i][j] = -1; } else { isDecreasing[i][j] = isDecreasing[i - 1][DP[i - 1][j]]; } if(isIncreasing[i - 1][j] == -1 || isIncreasing[i - 1][DP[i - 1][j]] == -1) { isIncreasing[i][j] = -1; } else if(isIncreasing[i - 1][j] >= isIncreasing[0][DP[i - 1][j]]) { isIncreasing[i][j] = -1; } else { isIncreasing[i][j] = isIncreasing[i - 1][DP[i - 1][j]]; } } } } /*for(int i = 0; i < 20; i++) { for(int j = 1; j <= n; j++) { cout << isIncreasing[i][j] << " "; } cout << "\n"; } for(int i = 0; i < 20; i++) { for(int j = 1; j <= n; j++) { cout << isDecreasing[i][j] << " "; } cout << "\n"; }*/ cnt = 0; int val[n + 1]; for(int i = 0; i <= n; i++) { val[i] = -1; } for(int i = 0; i < queries.size(); i++) { char c = queries[i].first; int a = queries[i].second.first, b = queries[i].second.second; if(c == 'S') { cnt++; if(a == 1) swap(a, b); val[a] = cnt - 1; } else if(c == 'Q') { if(Satisfied(a, b, cnt)) { cout << "yes\n"; } else { cout << "no\n"; } } else { if(a == 1) { cout << cnt + 1 << "\n"; } else { if(val[a] == -1) { cout << "1\n"; } else { cout << cnt - val[a] + 1 << "\n"; } } } } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while(t--) { Solve(); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In function 'void dfs(long long int, long long int)':
servers.cpp:14:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
servers.cpp: In function 'long long int dfs2(long long int, long long int, long long int, long long int)':
servers.cpp:93:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
servers.cpp: In function 'void Solve()':
servers.cpp:187:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<char, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |  for(int i = 0; i < queries.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
#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...