oj.uz

Submission #417567

# Submission time Handle Problem Language Result Execution time Memory
417567 2021-06-04T00:55:10 Z jainbot27 Inside information (BOI21_servers) C++17
100 / 100
 603 ms 55816 KB 
// Inside Information

/*
    how to solve queries of is A at B:

    basically we can just note that 
    we are looking at at a tree, find LCA of (A, B) 
    A has to be decreasing to whatever value we care about 
    B has to be increasing , max has to be less than time of query 

    O(nLOGn) or even constant with the other version of LCA that i dont know how to code

    also be careful of special cases on the LCA 
    
    how to solve the other kind of queries
    

*/


#include <bits/stdc++.h>
using namespace std;

using ll=long long;

#define FOR(i, a, b) for(int i=a; i<b; i++) 
#define ROF(i, a, b) for(int i=b-1; i>=a; i--)
#define F0R(i, n) FOR(i, 0, n) 
#define R0F(i, n) ROF(i, 0, n) 

#define f first
#define s second
#define pb push_back
#define siz(x) (int)x.size() 
#define ar array

const int mxN=2.4e5+10;
const int LG=20;

int n, q;
ar<int, 3> qq[mxN];
vector<pair<int, int>> adj[mxN];
int depth[mxN];
int anc[mxN][LG];
int mx[mxN][LG];

int mX[mxN], mN[mxN];

template<class T>void ckmax(T&A, T B){
    A=max(A, B);
}

void dfs(int u, int p, int c=-1){
    anc[u][0]=p; mx[u][0]=c;
    FOR(i, 1, LG){
        if(anc[u][i-1]==-1) anc[u][i]=-1, mx[u][i]=-1;
        else anc[u][i]=anc[anc[u][i-1]][i-1], mx[u][i]=max(mx[u][i-1], mx[anc[u][i-1]][i-1]);
    }
    for(auto[v, w]:adj[u]){
        if(v==p) continue;
        depth[v]=depth[u]+1;
        dfs(v, u, w);
    }
}

void dfs2(int u, int p, int L, int MX, int MN){
    mX[u]=MX, mN[u]=MN;
    for(auto[v, w]:adj[u]){
        if(v==p) continue;
        int nx=MX, ny=MN;
        if(w<L) nx=depth[u];
        if(w>L) ny=depth[u];
        dfs2(v, u, w, nx, ny);
    }
}

pair<int, int> lft(int u, int d){
    int maxx=0;
    for(int i=0; i<LG; i++){
        if(d&(1<<i)) ckmax(maxx, mx[u][i]), u=anc[u][i];
    }
    return {u, maxx};
}

pair<int, int> lca(int X, int Y){
    if(depth[X]<depth[Y]) swap(X, Y); 
    auto[XXX, maxx]=lft(X, depth[X]-depth[Y]);
    X=XXX;
    if(X==Y) return {X, maxx};
    R0F(i, LG){
        if(anc[X][i]!=anc[Y][i]){
            ckmax(maxx, mx[X][i]); 
            ckmax(maxx, mx[Y][i]); 
            X=anc[X][i]; Y=anc[Y][i];
        }
    }
    ckmax(maxx, mx[X][0]);
    ckmax(maxx, mx[Y][0]);
    return {anc[X][0], maxx};
}

int qry(int A, int B, int T){
    auto[L, V]=lca(A, B);
    // cout << A << ' ' << B << ' ' << L << ' ' << V << ' ' << i << "\n";
    if(V>T){
        return 0;
    }
    if(mN[A]<=depth[L]&&mX[B]<=depth[L]){
        if(A==L||B==L){
            return 1;
        }
        else{
            int AA=lft(A, depth[A]-depth[L]-1).f, BB=lft(B, depth[B]-depth[L]-1).f;
            if(mx[AA][0]<mx[BB][0]) return 1;
            else return 0;
        }
    }
    else
        return 0;
}

const int MOD=1e9+7; 

int par[mxN], sz[mxN], vis[mxN];
vector<int> proc[mxN];

int bit[mxN];

int occdfs3=0, occdfs4=0, occdfs5, occfindcent=0;

void upd(int x, int v){
    for(x++; x<mxN; x+=x&-x) 
        bit[x]+=v;
}
int qry(int x){
    int r=0;
    for(x++; x; x-=x&-x)
        r+=bit[x];
    return r;
}

int dfs3(int u, int p){
    if(vis[u]) return 0; 
    // cout << "DFS3: " << u << ' ' << p << endl;
    occdfs3++; 
    sz[u]=1;
    for(auto [v, w]:adj[u]){
        if(v==p) continue;
        sz[u]+=dfs3(v, u);
    }
    return sz[u];
}

int find_cent(int u, int p, int SZ){
    // cout << "FIND_CENT: " << u << ' ' << p << endl;
    occfindcent++;
    for(auto[v, w]:adj[u]){
        if(!vis[v]&&v!=p&&sz[v]>SZ/2){
            return find_cent(v, u, SZ); 
        }
    }
    return u;
}

int in[mxN];

void dfs4(int u, int t, int p, int DIF){
    // cout << "DFS4: " << u << ' ' << p << endl;
    occdfs4++; 
    in[u]=(DIF==1?t:MOD);
    upd(t, DIF);
    for(auto[v, w]:adj[u]) 
        if(v!=p&&!vis[v]) 
            if(w>=t)
                dfs4(v, w, u, DIF);
}

void solve(int u){
    for(auto v:proc[u]){
        // cout << v << ' ' << u << ' ' << qry(v) <<  "\n";
        qq[v][2]+=qry(v);
    }
}

void dfs5(int u, int t, int p){
    // cout << "DFS5: " << u <<  " " << t << " " << p << "\n";
    occdfs5++; 
    solve(u);
    for(auto[v, w]:adj[u]) 
        if(v!=p&&!vis[v]) 
            if(w<t)
                dfs5(v, w, u);
}

void cent(int u){
    dfs3(u, -1);
    // cout << "HERE" << endl;
    // cout << sz[u] << "\n";
    int c=find_cent(u, -1, sz[u]);
    // cout << u <<' ' << c << ' ' << sz[c] <<  ' ' << occdfs3 << ' '<< occdfs4 << ' ' << occdfs5 << ' ' << occfindcent << endl;
    // cout << c << endl;
    sort(adj[c].begin(), adj[c].end(), [&](const pair<int, int>&X, const pair<int, int>&Y){
        return X.s<Y.s;
    });
    vis[c]=1; 
    dfs4(c, 0, -1, 1);
    solve(c);
    for(auto[v, w]:adj[c]){
        if(vis[v]) continue;
        // cout << "??? " << v << ' ' << w << "\n";
        dfs4(v, w, c, -1);
        upd(in[c], -1);
        upd(in[c]=w, 1);
        dfs5(v, w, c);
    }
    upd(in[c], -1);
    in[c]=MOD;
    for(auto[v, w]:adj[c])
        if(!vis[v])
            cent(v);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    F0R(i, n+q-1){
        char T; cin >> T;
        if(T=='S'){
            int X, Y; cin >> X >> Y; X--; Y--; 
            adj[X].pb({Y, i}); 
            adj[Y].pb({X, i});
            qq[i]={1, X, Y};
        }
        else if(T=='Q'){
            int A, B; cin >> A >> B; A--; B--; 
            qq[i]={2, A, B};
        }
        else{
            int C; cin >> C; C--; 
            proc[C].pb(i);
            qq[i]={3, C, 0};
        }
    }
    memset(in, 0x3f, sizeof in);
    dfs(0, -1);
    dfs2(0, -1, 0, 0, 0);
    // F0R(i, n){
    //     // cout << mx[i][0] << ' ';
    //     cout << mX[i] << ' ' << mN[i] << "\n";
    // }
    // cout << "\n";
    cent(0);
    F0R(i, n+q-1){
        if(qq[i][0]==2){
            int A=qq[i][1], B=qq[i][2];
            swap(A, B);
            cout << (qry(A, B, i)?"yes":"no") << "\n";
        }
        else if(qq[i][0]==3){
            cout << qq[i][2] << "\n";
        }
    }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14588 KB Output is correct
2 Correct 58 ms 15716 KB Output is correct
3 Correct 59 ms 15804 KB Output is correct
4 Correct 67 ms 15940 KB Output is correct
5 Correct 57 ms 15500 KB Output is correct
6 Correct 60 ms 15444 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14588 KB Output is correct
2 Correct 58 ms 15716 KB Output is correct
3 Correct 59 ms 15804 KB Output is correct
4 Correct 67 ms 15940 KB Output is correct
5 Correct 57 ms 15500 KB Output is correct
6 Correct 60 ms 15444 KB Output is correct
7 Correct 46 ms 14684 KB Output is correct
8 Correct 56 ms 16056 KB Output is correct
9 Correct 54 ms 16156 KB Output is correct
10 Correct 59 ms 16228 KB Output is correct
11 Correct 57 ms 15912 KB Output is correct
12 Correct 53 ms 15872 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14672 KB Output is correct
2 Correct 201 ms 42484 KB Output is correct
3 Correct 197 ms 45308 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14672 KB Output is correct
2 Correct 201 ms 42484 KB Output is correct
3 Correct 197 ms 45308 KB Output is correct
4 Correct 48 ms 15588 KB Output is correct
5 Correct 197 ms 45412 KB Output is correct
6 Correct 148 ms 44984 KB Output is correct
7 Correct 154 ms 45112 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14632 KB Output is correct
2 Correct 279 ms 50952 KB Output is correct
3 Correct 272 ms 51020 KB Output is correct
4 Correct 267 ms 50880 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14632 KB Output is correct
2 Correct 279 ms 50952 KB Output is correct
3 Correct 272 ms 51020 KB Output is correct
4 Correct 267 ms 50880 KB Output is correct
5 Correct 42 ms 14708 KB Output is correct
6 Correct 311 ms 52420 KB Output is correct
7 Correct 293 ms 52420 KB Output is correct
8 Correct 321 ms 53048 KB Output is correct
9 Correct 314 ms 53116 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14640 KB Output is correct
2 Correct 245 ms 42264 KB Output is correct
3 Correct 236 ms 43012 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14640 KB Output is correct
2 Correct 245 ms 42264 KB Output is correct
3 Correct 236 ms 43012 KB Output is correct
4 Correct 47 ms 14644 KB Output is correct
5 Correct 278 ms 43864 KB Output is correct
6 Correct 258 ms 43920 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14648 KB Output is correct
2 Correct 297 ms 50976 KB Output is correct
3 Correct 267 ms 51008 KB Output is correct
4 Correct 272 ms 51156 KB Output is correct
5 Correct 48 ms 14684 KB Output is correct
6 Correct 242 ms 42188 KB Output is correct
7 Correct 235 ms 42948 KB Output is correct
8 Correct 317 ms 42948 KB Output is correct
9 Correct 291 ms 46656 KB Output is correct
10 Correct 393 ms 51232 KB Output is correct
11 Correct 422 ms 50148 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14648 KB Output is correct
2 Correct 297 ms 50976 KB Output is correct
3 Correct 267 ms 51008 KB Output is correct
4 Correct 272 ms 51156 KB Output is correct
5 Correct 48 ms 14684 KB Output is correct
6 Correct 242 ms 42188 KB Output is correct
7 Correct 235 ms 42948 KB Output is correct
8 Correct 317 ms 42948 KB Output is correct
9 Correct 291 ms 46656 KB Output is correct
10 Correct 393 ms 51232 KB Output is correct
11 Correct 422 ms 50148 KB Output is correct
12 Correct 42 ms 15536 KB Output is correct
13 Correct 330 ms 55348 KB Output is correct
14 Correct 294 ms 55508 KB Output is correct
15 Correct 327 ms 55672 KB Output is correct
16 Correct 317 ms 55660 KB Output is correct
17 Correct 46 ms 15620 KB Output is correct
18 Correct 277 ms 46772 KB Output is correct
19 Correct 257 ms 46936 KB Output is correct
20 Correct 322 ms 47312 KB Output is correct
21 Correct 309 ms 47656 KB Output is correct
22 Correct 450 ms 50756 KB Output is correct
23 Correct 535 ms 50868 KB Output is correct
24 Correct 457 ms 49936 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14568 KB Output is correct
2 Correct 60 ms 15752 KB Output is correct
3 Correct 67 ms 15804 KB Output is correct
4 Correct 65 ms 15832 KB Output is correct
5 Correct 59 ms 15516 KB Output is correct
6 Correct 61 ms 15412 KB Output is correct
7 Correct 51 ms 14652 KB Output is correct
8 Correct 202 ms 42584 KB Output is correct
9 Correct 199 ms 45372 KB Output is correct
10 Correct 43 ms 15556 KB Output is correct
11 Correct 298 ms 54312 KB Output is correct
12 Correct 277 ms 54340 KB Output is correct
13 Correct 279 ms 54236 KB Output is correct
14 Correct 44 ms 15556 KB Output is correct
15 Correct 256 ms 45512 KB Output is correct
16 Correct 250 ms 46404 KB Output is correct
17 Correct 339 ms 46208 KB Output is correct
18 Correct 332 ms 46660 KB Output is correct
19 Correct 386 ms 51164 KB Output is correct
20 Correct 471 ms 50248 KB Output is correct
21 Correct 239 ms 45876 KB Output is correct
22 Correct 252 ms 45916 KB Output is correct
23 Correct 309 ms 46180 KB Output is correct
24 Correct 295 ms 46300 KB Output is correct
25 Correct 387 ms 49092 KB Output is correct
26 Correct 328 ms 45796 KB Output is correct
27 Correct 335 ms 45712 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14568 KB Output is correct
2 Correct 60 ms 15752 KB Output is correct
3 Correct 67 ms 15804 KB Output is correct
4 Correct 65 ms 15832 KB Output is correct
5 Correct 59 ms 15516 KB Output is correct
6 Correct 61 ms 15412 KB Output is correct
7 Correct 51 ms 14652 KB Output is correct
8 Correct 202 ms 42584 KB Output is correct
9 Correct 199 ms 45372 KB Output is correct
10 Correct 43 ms 15556 KB Output is correct
11 Correct 298 ms 54312 KB Output is correct
12 Correct 277 ms 54340 KB Output is correct
13 Correct 279 ms 54236 KB Output is correct
14 Correct 44 ms 15556 KB Output is correct
15 Correct 256 ms 45512 KB Output is correct
16 Correct 250 ms 46404 KB Output is correct
17 Correct 339 ms 46208 KB Output is correct
18 Correct 332 ms 46660 KB Output is correct
19 Correct 386 ms 51164 KB Output is correct
20 Correct 471 ms 50248 KB Output is correct
21 Correct 239 ms 45876 KB Output is correct
22 Correct 252 ms 45916 KB Output is correct
23 Correct 309 ms 46180 KB Output is correct
24 Correct 295 ms 46300 KB Output is correct
25 Correct 387 ms 49092 KB Output is correct
26 Correct 328 ms 45796 KB Output is correct
27 Correct 335 ms 45712 KB Output is correct
28 Correct 48 ms 15556 KB Output is correct
29 Correct 58 ms 17184 KB Output is correct
30 Correct 58 ms 17228 KB Output is correct
31 Correct 65 ms 17296 KB Output is correct
32 Correct 59 ms 17036 KB Output is correct
33 Correct 54 ms 16964 KB Output is correct
34 Correct 48 ms 15556 KB Output is correct
35 Correct 227 ms 45308 KB Output is correct
36 Correct 167 ms 44948 KB Output is correct
37 Correct 169 ms 45112 KB Output is correct
38 Correct 44 ms 15560 KB Output is correct
39 Correct 347 ms 55448 KB Output is correct
40 Correct 318 ms 55492 KB Output is correct
41 Correct 372 ms 55816 KB Output is correct
42 Correct 354 ms 55712 KB Output is correct
43 Correct 47 ms 15576 KB Output is correct
44 Correct 286 ms 46708 KB Output is correct
45 Correct 278 ms 46916 KB Output is correct
46 Correct 360 ms 47380 KB Output is correct
47 Correct 342 ms 47716 KB Output is correct
48 Correct 508 ms 50804 KB Output is correct
49 Correct 603 ms 50884 KB Output is correct
50 Correct 514 ms 49864 KB Output is correct
51 Correct 200 ms 46132 KB Output is correct
52 Correct 180 ms 45896 KB Output is correct
53 Correct 177 ms 45564 KB Output is correct
54 Correct 179 ms 46072 KB Output is correct
55 Correct 189 ms 45892 KB Output is correct
56 Correct 284 ms 46164 KB Output is correct
57 Correct 359 ms 49144 KB Output is correct
58 Correct 445 ms 47020 KB Output is correct
59 Correct 361 ms 46148 KB Output is correct