oj.uz

Submission #402715

# Submission time Handle Problem Language Result Execution time Memory
402715 2021-05-12T09:41:28 Z rrrr10000 Inside information (BOI21_servers) C++14
100 / 100
 696 ms 39652 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
class BIT{
    vi bit;ll N;
public:
    ll sum(ll i){
        chmin(i,N);
        ll res=0;
        for(ll j=i-1;j>=0;j=(j&(j+1))-1)res+=bit[j];
        return res;
    }
    BIT(ll n):N(n){bit.resize(N);}
    void add(ll i,ll x){
        for(int j=i;j<N;j|=j+1)bit[j]+=x;
    }
    ll get(ll a,ll b){
        return sum(b)-sum(a);
    }
};
class UF{
    vi data;stack<P> st;
public:
    UF(ll n){
        data=vi(n,1);
    }
    bool merge(ll x,ll y,bool undo=false){
        x=root(x);y=root(y);
        if(data[x]>data[y])swap(x,y);
        if(undo){st.emplace(y,data[y]);st.emplace(x,data[x]);}
        if(x==y)return false;
        data[y]+=data[x];data[x]=-y;
        return true;
    }
    ll root(ll i){if(data[i]>0)return i;return root(-data[i]);}
    ll getsize(ll i){return data[root(i)];}
    bool same(ll a,ll b){return root(a)==root(b);}
    void undo(){rep(i,2){data[st.top().fi]=st.top().se;st.pop();}}
};
int main(){
    ll n,q;cin>>n>>q;
    vvp g(n);
    ll cur=0,cnt_query=0;
    vi ans(q);
    UF uf(n);
    vvp q1(n),q2(n);
    rep(i,q+n-1){
        char c;cin>>c;
        if(c=='S'){
            ll a,b;cin>>a>>b;a--;b--;
            g[a].pb(cur,b);g[b].pb(cur,a);cur++;
            uf.merge(a,b);
        }
        if(c=='Q'){
            ll a,b;cin>>a>>b;a--;b--;
            if(uf.same(a,b))q1[b].pb(a,cnt_query);
            ans[cnt_query++]=-2;
        }
        if(c=='C'){
            ll a;cin>>a;a--;
            q2[a].pb(cur,cnt_query++);
        }
    }
    rep(i,n)rsort(g[i]);
    vb dead(n,false);vi sub(n);
    function<ll(ll,ll,ll)> find_cen=[&](ll i,ll p,ll s){
        for(auto x:g[i])if(!dead[x.se]&&x.se!=p&&sub[x.se]*2>s)return find_cen(x.se,i,s);
        return i;
    };
    function<ll(ll,ll)> init=[&](ll i,ll p){
        sub[i]=1;
        for(auto x:g[i])if(!dead[x.se]&&x.se!=p)sub[i]+=init(x.se,i);
        return sub[i];
    };
    auto getcen=[&](ll i){
        init(i,-1);
        return find_cen(i,-1,sub[i]);
    };
    BIT bit(n);
    vb ok(n,false);
    function<void(ll)> solve=[&](ll c){
        vi tmp,tmp2;
        c=getcen(c);
        ok[c]=true;tmp2.pb(c);
        rep(idx,g[c].size())if(!dead[g[c][idx].se]){
            queue<PP> que;
            que.emplace(g[c][idx].se,g[c][idx].fi,-1);
            while(!que.empty()){
                ll i,prev,par;tie(i,prev,par)=que.front();que.pop();
                for(auto x:q1[i]){
                    if(ok[x.fi])ans[x.se]=-1;
                }
                for(auto x:q2[i]){
                    if(g[c][idx].fi<x.fi)ans[x.se]+=bit.sum(x.fi)+1;
                }
                for(auto x:g[i])if(x.se!=par&&!dead[x.se]&&x.fi<prev){
                    que.emplace(x.se,x.fi,i);
                }
            }
            que.emplace(g[c][idx].se,g[c][idx].fi,-1);
            while(!que.empty()){
                ll i,prev,par;tie(i,prev,par)=que.front();que.pop();ok[i]=true;tmp2.pb(i);
                bit.add(prev,1);tmp.pb(prev);
                for(auto x:g[i])if(x.se!=par&&!dead[x.se]&&x.fi>prev){
                    que.emplace(x.se,x.fi,i);
                }
            }
        }
        for(auto x:q1[c]){
            if(ok[x.fi])ans[x.se]=-1;
        }
        for(auto x:q2[c]){
            ans[x.se]+=bit.sum(x.fi)+1;
        }
        for(ll x:tmp)bit.add(x,-1);for(ll x:tmp2)ok[x]=false;
        dead[c]=true;
        for(auto x:g[c])if(!dead[x.se])solve(x.se);
    };solve(0);
    for(ll x:ans){
        if(x==-1)out("yes");
        else if(x==-2)out("no");
        else out(x);
    }
}

Compilation message

servers.cpp: In lambda function:
servers.cpp:161:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  161 |         for(ll x:tmp)bit.add(x,-1);for(ll x:tmp2)ok[x]=false;
      |         ^~~
servers.cpp:161:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  161 |         for(ll x:tmp)bit.add(x,-1);for(ll x:tmp2)ok[x]=false;
      |                                    ^~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2260 KB Output is correct
2 Correct 98 ms 3784 KB Output is correct
3 Correct 109 ms 6356 KB Output is correct
4 Correct 98 ms 3656 KB Output is correct
5 Correct 107 ms 7220 KB Output is correct
6 Correct 105 ms 6740 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2260 KB Output is correct
2 Correct 98 ms 3784 KB Output is correct
3 Correct 109 ms 6356 KB Output is correct
4 Correct 98 ms 3656 KB Output is correct
5 Correct 107 ms 7220 KB Output is correct
6 Correct 105 ms 6740 KB Output is correct
7 Correct 73 ms 2440 KB Output is correct
8 Correct 88 ms 4820 KB Output is correct
9 Correct 84 ms 5852 KB Output is correct
10 Correct 101 ms 4836 KB Output is correct
11 Correct 93 ms 6808 KB Output is correct
12 Correct 84 ms 6072 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 2704 KB Output is correct
2 Correct 354 ms 27376 KB Output is correct
3 Correct 319 ms 27468 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 2704 KB Output is correct
2 Correct 354 ms 27376 KB Output is correct
3 Correct 319 ms 27468 KB Output is correct
4 Correct 75 ms 3532 KB Output is correct
5 Correct 306 ms 26984 KB Output is correct
6 Correct 242 ms 24940 KB Output is correct
7 Correct 225 ms 25304 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2252 KB Output is correct
2 Correct 473 ms 39040 KB Output is correct
3 Correct 479 ms 39000 KB Output is correct
4 Correct 430 ms 39592 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2252 KB Output is correct
2 Correct 473 ms 39040 KB Output is correct
3 Correct 479 ms 39000 KB Output is correct
4 Correct 430 ms 39592 KB Output is correct
5 Correct 84 ms 3016 KB Output is correct
6 Correct 469 ms 38856 KB Output is correct
7 Correct 474 ms 39312 KB Output is correct
8 Correct 493 ms 38228 KB Output is correct
9 Correct 437 ms 38340 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2276 KB Output is correct
2 Correct 417 ms 28136 KB Output is correct
3 Correct 413 ms 26328 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2276 KB Output is correct
2 Correct 417 ms 28136 KB Output is correct
3 Correct 413 ms 26328 KB Output is correct
4 Correct 71 ms 3040 KB Output is correct
5 Correct 421 ms 28096 KB Output is correct
6 Correct 458 ms 25872 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2148 KB Output is correct
2 Correct 482 ms 39108 KB Output is correct
3 Correct 502 ms 38972 KB Output is correct
4 Correct 514 ms 39652 KB Output is correct
5 Correct 72 ms 3176 KB Output is correct
6 Correct 408 ms 28160 KB Output is correct
7 Correct 433 ms 26372 KB Output is correct
8 Correct 481 ms 26792 KB Output is correct
9 Correct 446 ms 26948 KB Output is correct
10 Correct 593 ms 32256 KB Output is correct
11 Correct 557 ms 31324 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2148 KB Output is correct
2 Correct 482 ms 39108 KB Output is correct
3 Correct 502 ms 38972 KB Output is correct
4 Correct 514 ms 39652 KB Output is correct
5 Correct 72 ms 3176 KB Output is correct
6 Correct 408 ms 28160 KB Output is correct
7 Correct 433 ms 26372 KB Output is correct
8 Correct 481 ms 26792 KB Output is correct
9 Correct 446 ms 26948 KB Output is correct
10 Correct 593 ms 32256 KB Output is correct
11 Correct 557 ms 31324 KB Output is correct
12 Correct 72 ms 3044 KB Output is correct
13 Correct 472 ms 38716 KB Output is correct
14 Correct 456 ms 39364 KB Output is correct
15 Correct 544 ms 38340 KB Output is correct
16 Correct 480 ms 38232 KB Output is correct
17 Correct 70 ms 3096 KB Output is correct
18 Correct 421 ms 28016 KB Output is correct
19 Correct 422 ms 25924 KB Output is correct
20 Correct 510 ms 26600 KB Output is correct
21 Correct 457 ms 26856 KB Output is correct
22 Correct 572 ms 30652 KB Output is correct
23 Correct 667 ms 32460 KB Output is correct
24 Correct 638 ms 32292 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 75 ms 2152 KB Output is correct
2 Correct 96 ms 3796 KB Output is correct
3 Correct 98 ms 6352 KB Output is correct
4 Correct 95 ms 3732 KB Output is correct
5 Correct 106 ms 7260 KB Output is correct
6 Correct 103 ms 6860 KB Output is correct
7 Correct 73 ms 3660 KB Output is correct
8 Correct 334 ms 27288 KB Output is correct
9 Correct 342 ms 27268 KB Output is correct
10 Correct 72 ms 3064 KB Output is correct
11 Correct 507 ms 38984 KB Output is correct
12 Correct 526 ms 38976 KB Output is correct
13 Correct 451 ms 39588 KB Output is correct
14 Correct 72 ms 3156 KB Output is correct
15 Correct 419 ms 28300 KB Output is correct
16 Correct 443 ms 26264 KB Output is correct
17 Correct 465 ms 26824 KB Output is correct
18 Correct 516 ms 27044 KB Output is correct
19 Correct 592 ms 32248 KB Output is correct
20 Correct 577 ms 31224 KB Output is correct
21 Correct 380 ms 28220 KB Output is correct
22 Correct 378 ms 27432 KB Output is correct
23 Correct 399 ms 26032 KB Output is correct
24 Correct 415 ms 26052 KB Output is correct
25 Correct 515 ms 33252 KB Output is correct
26 Correct 467 ms 25576 KB Output is correct
27 Correct 480 ms 25652 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 75 ms 2152 KB Output is correct
2 Correct 96 ms 3796 KB Output is correct
3 Correct 98 ms 6352 KB Output is correct
4 Correct 95 ms 3732 KB Output is correct
5 Correct 106 ms 7260 KB Output is correct
6 Correct 103 ms 6860 KB Output is correct
7 Correct 73 ms 3660 KB Output is correct
8 Correct 334 ms 27288 KB Output is correct
9 Correct 342 ms 27268 KB Output is correct
10 Correct 72 ms 3064 KB Output is correct
11 Correct 507 ms 38984 KB Output is correct
12 Correct 526 ms 38976 KB Output is correct
13 Correct 451 ms 39588 KB Output is correct
14 Correct 72 ms 3156 KB Output is correct
15 Correct 419 ms 28300 KB Output is correct
16 Correct 443 ms 26264 KB Output is correct
17 Correct 465 ms 26824 KB Output is correct
18 Correct 516 ms 27044 KB Output is correct
19 Correct 592 ms 32248 KB Output is correct
20 Correct 577 ms 31224 KB Output is correct
21 Correct 380 ms 28220 KB Output is correct
22 Correct 378 ms 27432 KB Output is correct
23 Correct 399 ms 26032 KB Output is correct
24 Correct 415 ms 26052 KB Output is correct
25 Correct 515 ms 33252 KB Output is correct
26 Correct 467 ms 25576 KB Output is correct
27 Correct 480 ms 25652 KB Output is correct
28 Correct 73 ms 3180 KB Output is correct
29 Correct 89 ms 4836 KB Output is correct
30 Correct 90 ms 5856 KB Output is correct
31 Correct 89 ms 4892 KB Output is correct
32 Correct 98 ms 6848 KB Output is correct
33 Correct 85 ms 6032 KB Output is correct
34 Correct 71 ms 3524 KB Output is correct
35 Correct 316 ms 26992 KB Output is correct
36 Correct 221 ms 24972 KB Output is correct
37 Correct 248 ms 25296 KB Output is correct
38 Correct 77 ms 3056 KB Output is correct
39 Correct 468 ms 38808 KB Output is correct
40 Correct 474 ms 39380 KB Output is correct
41 Correct 467 ms 38296 KB Output is correct
42 Correct 519 ms 38344 KB Output is correct
43 Correct 76 ms 3028 KB Output is correct
44 Correct 424 ms 28116 KB Output is correct
45 Correct 483 ms 26028 KB Output is correct
46 Correct 464 ms 26608 KB Output is correct
47 Correct 465 ms 26732 KB Output is correct
48 Correct 586 ms 30608 KB Output is correct
49 Correct 696 ms 32520 KB Output is correct
50 Correct 655 ms 32188 KB Output is correct
51 Correct 277 ms 27096 KB Output is correct
52 Correct 311 ms 26212 KB Output is correct
53 Correct 250 ms 25652 KB Output is correct
54 Correct 257 ms 26112 KB Output is correct
55 Correct 264 ms 26288 KB Output is correct
56 Correct 372 ms 25260 KB Output is correct
57 Correct 402 ms 31788 KB Output is correct
58 Correct 506 ms 25160 KB Output is correct
59 Correct 462 ms 25640 KB Output is correct