oj.uz

Submission #599656

# Submission time Handle Problem Language Result Execution time Memory
599656 2022-07-19T17:56:35 Z MohammadAghil Inside information (BOI21_servers) C++17
50 / 100
 450 ms 45740 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) begin(x), end(x)
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      freopen("in.in", "r", stdin);
     //      freopen("out.out", "w", stdout);
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 3e5 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
 
int fen[maxn];
vector<int> his;
void upd(int i, bool add = true){
     if(add) his.pb(i);
     for(i++; i < maxn; i += i&-i) fen[i] += add?1:-1;
}
int get(int i){
     int res = 0;
     for(i++; i; i -= i&-i) res += fen[i];
     return res;
}
 
vector<pp> adj[maxn];
vector<pp> query1[maxn];
vector<int> query2[maxn];
int cnt[maxn], id[maxn], tp[maxn], ans[maxn], n;
bool ban[maxn], rc[maxn], cr[maxn];
 
void dfs(int r, int p = -1, bool st = true){ //
     cnt[r] = st?1:-1;
     for(auto[c, t]: adj[r]) if(!ban[c] && c - p) dfs(c, r, st), cnt[r] += st?cnt[c]:0;
}

int find_cent(int r, int p, int tot){ //
     for(auto[c, t]: adj[r]) if(c - p && !ban[c] && (cnt[c]<<1) > tot) return find_cent(c, r, tot);
     return r;
}
 
void dfs2(int r, int p, int ID){
     id[r] = ID;
     if(r - ID){
          rc[r] = rc[p]&(tp[r] > tp[p]);
          cr[r] = cr[p]&(tp[r] < tp[p]);
     }
     for(auto[c, t]: adj[r]) if(c - p && !ban[c]) tp[c] = t, dfs2(c, r, ID); 
}
 
vector<int> tmp;
 
void dfs3(int r, int p){
     if(rc[r]) tmp.pb(tp[r]);
     for(auto[c, t]: query1[r]) if(cnt[c] + 1 && id[c] == -1){
          ans[t] = cr[r]&(tp[id[r]] < t);
     } else if(cnt[c] + 1 && tp[id[c]] > tp[id[r]]){
          ans[t] = cr[r]&rc[c]&(tp[c] < t);
     }
     for(int t: query2[r]) if(cr[r] && tp[id[r]] < t){
          ans[t] += get(t);
     }
     for(auto[c, t]: adj[r]) if(c - p && !ban[c]) dfs3(c, r);
}
 
void reset(int r){
     for(int c: his) upd(c, false);
     his.clear();
     dfs(r, -1, false);
     ban[r] = true;
}
 
void dec(int r){
     dfs(r);
     r = find_cent(r, -1, cnt[r]);
     sort(all(adj[r]), [&](pp a, pp b){ return a.ss > b.ss; });
     rc[r] = cr[r] = true, id[r] = -1;
     for(auto[c, t]: adj[r]) if(!ban[c]) rc[c] = cr[c] = true, tp[c] = t, dfs2(c, r, c);
     upd(r);
     for(auto[c, t]: adj[r]) if(!ban[c]){
          dfs3(c, r);
          for(int v: tmp) upd(v);
          tmp.clear();
     }
     for(auto[c, t]: query1[r]) if(cnt[c] + 1 && rc[c] && t > tp[c]) ans[t] = true;
     for(int t: query2[r]) ans[t] += get(t);
     reset(r);
     for(auto[c, t]: adj[r]) if(!ban[c]) dec(c);
}
 
int main(){ IOS();
     int k; cin >> n >> k;
     vector<int> ty(n+k);
     rep(i,0,n+k-1){
          char c; cin >> c;
          if(c == 'S'){
               int u, v; cin >> u >> v; u--, v--;
               adj[u].pb({v, i}), adj[v].pb({u, i});
          }else if(c == 'Q'){
               ty[i] = 1;
               int u, v; cin >> u >> v; u--, v--;
               if(u - v) query1[v].pb({u, i});
               else ans[i] = 1;
          }else{
               ty[i] = 2;
               int d; cin >> d; d--;
               query2[d].pb(i);
          }
     }
     dec(0);
     rep(i,0,n+k-1) if(ty[i]){
          if(ty[i]&1) cout << (ans[i]?"yes":"no") << '\n';
          else cout << ans[i] << '\n';
     }
     return 0; 
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24652 KB Output is correct
2 Correct 45 ms 25060 KB Output is correct
3 Correct 42 ms 26228 KB Output is correct
4 Correct 49 ms 26596 KB Output is correct
5 Correct 51 ms 26340 KB Output is correct
6 Correct 43 ms 26248 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24652 KB Output is correct
2 Correct 45 ms 25060 KB Output is correct
3 Correct 42 ms 26228 KB Output is correct
4 Correct 49 ms 26596 KB Output is correct
5 Correct 51 ms 26340 KB Output is correct
6 Correct 43 ms 26248 KB Output is correct
7 Correct 35 ms 25560 KB Output is correct
8 Incorrect 49 ms 25932 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24792 KB Output is correct
2 Correct 187 ms 34404 KB Output is correct
3 Correct 186 ms 34376 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24792 KB Output is correct
2 Correct 187 ms 34404 KB Output is correct
3 Correct 186 ms 34376 KB Output is correct
4 Correct 33 ms 24680 KB Output is correct
5 Incorrect 168 ms 34240 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24720 KB Output is correct
2 Correct 377 ms 41424 KB Output is correct
3 Correct 407 ms 44764 KB Output is correct
4 Correct 252 ms 45684 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24720 KB Output is correct
2 Correct 377 ms 41424 KB Output is correct
3 Correct 407 ms 44764 KB Output is correct
4 Correct 252 ms 45684 KB Output is correct
5 Correct 42 ms 25508 KB Output is correct
6 Incorrect 421 ms 45092 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24708 KB Output is correct
2 Correct 237 ms 33804 KB Output is correct
3 Correct 296 ms 36088 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24708 KB Output is correct
2 Correct 237 ms 33804 KB Output is correct
3 Correct 296 ms 36088 KB Output is correct
4 Correct 34 ms 25536 KB Output is correct
5 Incorrect 262 ms 37292 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 24728 KB Output is correct
2 Correct 390 ms 41588 KB Output is correct
3 Correct 406 ms 44876 KB Output is correct
4 Correct 260 ms 45664 KB Output is correct
5 Correct 33 ms 25508 KB Output is correct
6 Correct 242 ms 37060 KB Output is correct
7 Correct 306 ms 36168 KB Output is correct
8 Correct 342 ms 37272 KB Output is correct
9 Correct 337 ms 37224 KB Output is correct
10 Correct 370 ms 40904 KB Output is correct
11 Correct 382 ms 39688 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 24728 KB Output is correct
2 Correct 390 ms 41588 KB Output is correct
3 Correct 406 ms 44876 KB Output is correct
4 Correct 260 ms 45664 KB Output is correct
5 Correct 33 ms 25508 KB Output is correct
6 Correct 242 ms 37060 KB Output is correct
7 Correct 306 ms 36168 KB Output is correct
8 Correct 342 ms 37272 KB Output is correct
9 Correct 337 ms 37224 KB Output is correct
10 Correct 370 ms 40904 KB Output is correct
11 Correct 382 ms 39688 KB Output is correct
12 Correct 33 ms 25632 KB Output is correct
13 Incorrect 395 ms 45024 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24736 KB Output is correct
2 Correct 44 ms 25164 KB Output is correct
3 Correct 40 ms 26220 KB Output is correct
4 Correct 49 ms 26560 KB Output is correct
5 Correct 48 ms 26316 KB Output is correct
6 Correct 42 ms 26232 KB Output is correct
7 Correct 34 ms 25548 KB Output is correct
8 Correct 172 ms 37184 KB Output is correct
9 Correct 172 ms 37184 KB Output is correct
10 Correct 33 ms 25572 KB Output is correct
11 Correct 366 ms 45052 KB Output is correct
12 Correct 374 ms 44836 KB Output is correct
13 Correct 255 ms 45740 KB Output is correct
14 Correct 33 ms 25548 KB Output is correct
15 Correct 236 ms 37144 KB Output is correct
16 Correct 284 ms 36064 KB Output is correct
17 Correct 334 ms 37324 KB Output is correct
18 Correct 361 ms 37216 KB Output is correct
19 Correct 375 ms 40840 KB Output is correct
20 Correct 392 ms 39672 KB Output is correct
21 Correct 183 ms 37820 KB Output is correct
22 Correct 220 ms 37416 KB Output is correct
23 Correct 278 ms 37048 KB Output is correct
24 Correct 254 ms 37224 KB Output is correct
25 Correct 450 ms 41464 KB Output is correct
26 Correct 336 ms 35140 KB Output is correct
27 Correct 291 ms 34956 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24736 KB Output is correct
2 Correct 44 ms 25164 KB Output is correct
3 Correct 40 ms 26220 KB Output is correct
4 Correct 49 ms 26560 KB Output is correct
5 Correct 48 ms 26316 KB Output is correct
6 Correct 42 ms 26232 KB Output is correct
7 Correct 34 ms 25548 KB Output is correct
8 Correct 172 ms 37184 KB Output is correct
9 Correct 172 ms 37184 KB Output is correct
10 Correct 33 ms 25572 KB Output is correct
11 Correct 366 ms 45052 KB Output is correct
12 Correct 374 ms 44836 KB Output is correct
13 Correct 255 ms 45740 KB Output is correct
14 Correct 33 ms 25548 KB Output is correct
15 Correct 236 ms 37144 KB Output is correct
16 Correct 284 ms 36064 KB Output is correct
17 Correct 334 ms 37324 KB Output is correct
18 Correct 361 ms 37216 KB Output is correct
19 Correct 375 ms 40840 KB Output is correct
20 Correct 392 ms 39672 KB Output is correct
21 Correct 183 ms 37820 KB Output is correct
22 Correct 220 ms 37416 KB Output is correct
23 Correct 278 ms 37048 KB Output is correct
24 Correct 254 ms 37224 KB Output is correct
25 Correct 450 ms 41464 KB Output is correct
26 Correct 336 ms 35140 KB Output is correct
27 Correct 291 ms 34956 KB Output is correct
28 Correct 34 ms 25504 KB Output is correct
29 Incorrect 46 ms 25820 KB Extra information in the output file
30 Halted 0 ms 0 KB -