제출 #1036715

#제출 시각아이디문제언어결과실행 시간메모리
1036715vjudge1Inside information (BOI21_servers)C++17
52.50 / 100
240 ms88568 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #define pb push_back #define pf push_front #define fi first #define se second const ll mod = 1e9+7, mxn_s1 = 4007, mxn_full = 12e4+7; ll n, q, cnt[mxn_s1], tl[mxn_full], h[mxn_full], up[mxn_full][20], mx[mxn_full][20], mn[mxn_full][20]; bool connected[mxn_full], lis[mxn_full][20], lds[mxn_full][20]; vector<vector<ll>> v(mxn_s1); vector<vector<pair<ll,ll>>> g(mxn_full); void dfs(ll u, ll v) { for (pair<ll,ll> i : g[u]) { if (i.fi != v) { h[i.fi] = h[u]+1; up[i.fi][0] = u; mx[i.fi][0] = mn[i.fi][0] = i.se; lis[i.fi][0] = lds[i.fi][0] = 1; dfs(i.fi,u); } } } void build_lca() { for (ll j = 1; j <= 19; j++) { for (ll i = 1; i <= n; i++) { mx[i][j] = max(mx[i][j-1],mx[up[i][j-1]][j-1]); mn[i][j] = min(mn[i][j-1],mn[up[i][j-1]][j-1]); lis[i][j] = (lis[i][j-1] && lis[up[i][j-1]][j-1] && (mx[i][j-1] < mn[up[i][j-1]][j-1])); lds[i][j] = (lds[i][j-1] && lds[up[i][j-1]][j-1] && (mn[i][j-1] > mx[up[i][j-1]][j-1])); up[i][j] = up[up[i][j-1]][j-1]; } } } ll lift(ll a, ll b) { for (ll i = 19; i >= 0; i--) if (b>>i&1) a = up[a][i]; return a; } bool lis_ck(ll a, ll b) { bool ck = 1; ll mxx = 0; for (ll i = 19; i >= 0; i--) if (b>>i&1) {ck &= (lis[a][i] && mn[a][i] > mxx); mxx = mx[a][i]; a = up[a][i];} return ck; } bool lds_ck(ll a, ll b) { bool ck = 1; ll mnn = 1e18; for (ll i = 19; i >= 0; i--) if (b>>i&1) {ck &= (lds[a][i] && mx[a][i] < mnn); mnn = mn[a][i]; a = up[a][i];} return ck; } ll lca(ll a, ll b) { if (h[a] != h[b]) { if (h[a] < h[b]) swap(a,b); ll k = h[a]-h[b]; for (ll i = __lg(k); i >= 0; i--) { if (k >> i & 1) a = up[a][i]; } } if (a == b) return a; for (ll i = 19; i >= 0; i--) { if (up[a][i] != up[b][i]) {a = up[a][i]; b = up[b][i];} } return up[a][0]; } ll rmx(ll a, ll b) { ll ans = 0; if (h[a] != h[b]) { if (h[a] < h[b]) swap(a,b); ll k = h[a]-h[b]; for (ll i = __lg(k); i >= 0; i--) { if (k >> i & 1) { ans = max(ans, mx[a][i]); a = up[a][i]; } } } if (a == b) return ans; for (ll i = 19; i >= 0; i--) { if (up[a][i] != up[b][i]) { ans = max({ans, mx[a][i], mx[b][i]}); a = up[a][i]; b = up[b][i]; } } return max({ans, mx[a][0], mx[b][0]}); } ll rmn(ll a, ll b) { ll ans = 1e18; if (h[a] != h[b]) { if (h[a] < h[b]) swap(a,b); ll k = h[a]-h[b]; for (ll i = __lg(k); i >= 0; i--) { if (k >> i & 1) { ans = min(ans, mn[a][i]); a = up[a][i]; } } } if (a == b) return ans; for (ll i = 19; i >= 0; i--) { if (up[a][i] != up[b][i]) { ans = min({ans, mn[a][i], mn[b][i]}); a = up[a][i]; b = up[b][i]; } } return min({ans, mn[a][0], mn[b][0]}); } struct query {char c; ll l, r;}; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr); cin >> n >> q; if (n <= 4000) { for (ll i = 1; i <= n; i++) {v[i].pb(i); cnt[i]++;} for (ll i = 1; i < q+n; i++) { char c; cin >> c; if (c == 'C') { ll x; cin >> x; cout << cnt[x] << '\n'; } else if (c == 'Q') { ll x, y; cin >> x >> y; bool ck = 0; for (ll j : v[x]) if (j == y) ck = 1; if (ck) cout << "yes" << '\n'; else cout << "no" << '\n'; } else { ll a, b; cin >> a >> b; if (v[a].size() > v[b].size()) swap(a,b); vector<ll> tmp = v[a]; for (ll j : v[b]) { v[a].pb(j); cnt[j]++; } for (ll j : tmp) { v[b].pb(j); cnt[j]++; } } } } else { vector<query> qx; bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1; for (ll i = 1; i < q+n; i++) { char c; cin >> c; if (c == 'C') { ll x; cin >> x; qx.pb({c,x,0}); } else if (c == 'Q') { ll x, y; cin >> x >> y; qx.pb({c,x,y}); } else { ll a, b; cin >> a >> b; if (a > b) swap(a,b); qx.pb({c,a,b}); if (a != 1) ck_s2 = 0; if (b-a != 1) ck_s3 = 0; if ((a<<1) != b && (a<<1|1) != b) ck_s4 = 0; } } if (0) // ck_s2 { ll cnt_connected = tl[1] = 1; for (query i : qx) { if (i.c == 'S') tl[i.r] = ++cnt_connected; else if (i.c == 'C') { if (i.l == 1) cout << cnt_connected << '\n'; else cout << cnt_connected-tl[i.l]+1 << '\n'; } else { if (i.l == i.r) cout << "yes" << '\n'; else if (i.l == 1) { if (tl[i.r]) cout << "yes" << '\n'; else cout << "no" << '\n'; } else if (i.r == 1) { if (tl[i.l]) cout << "yes" << '\n'; else cout << "no" << '\n'; } else if (!tl[i.l] || !tl[i.r]) cout << "no" << '\n'; else { if (tl[i.l] < tl[i.r]) cout << "no" << '\n'; else cout << "yes" << '\n'; } } } } else if (0) // ck_s3 { } else { // cerr << "50%" << '\n'; ll til = 0; for (query i : qx) { til++; if (i.c == 'S') { g[i.l].pb({i.r,til}); g[i.r].pb({i.l,til}); } } dfs(1,1); build_lca(); til = 0; // cerr << lds_ck(3,1); for (query i : qx) { til++; if (i.c == 'Q') { ll l = lca(i.l, i.r); ll dl = h[i.l]-h[l], dr = h[i.r]-h[l]; // cerr << i.l << ' ' << i.r << ' ' << l << ' ' << dl << ' ' << dr << '\n'; bool liss = lis_ck(i.r, dr), ldss = lds_ck(i.l, dl); // cerr << liss << ' ' << ldss << '\n'; if (liss && ldss && rmn(i.l,l) > rmx(i.r,l) && rmx(i.l,i.r) <= til) cout << "yes" << '\n'; else cout << "no" << '\n'; } } } } }

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

servers.cpp: In function 'int main()':
servers.cpp:176:14: warning: variable 'ck_s2' set but not used [-Wunused-but-set-variable]
  176 |         bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1;
      |              ^~~~~
servers.cpp:176:25: warning: variable 'ck_s3' set but not used [-Wunused-but-set-variable]
  176 |         bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1;
      |                         ^~~~~
servers.cpp:176:36: warning: variable 'ck_s4' set but not used [-Wunused-but-set-variable]
  176 |         bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1;
      |                                    ^~~~~
#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...