oj.uz

Submission #417563

# Submission time Handle Problem Language Result Execution time Memory
417563 2021-06-04T00:30:07 Z jainbot27 Inside information (BOI21_servers) C++17
35 / 100
 3500 ms 55772 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];

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; 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){
    for(auto[v, w]:adj[u]){
        if(!vis[v]&&v!=p&&sz[u]>SZ/2){
            return find_cent(v, u, SZ); 
        }
    }
    return u;
}

int in[mxN];

void dfs4(int u, int t, int p, int DIF){
    in[u]=t;
    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";
    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;
    int c=find_cent(u, -1, sz[u]);
    // 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";
        }
    }
}

Compilation message

servers.cpp: In function 'int dfs3(int, int)':
servers.cpp:141:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  141 |     if(vis[u]) return 0; sz[u]=1;
      |     ^~
servers.cpp:141:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  141 |     if(vis[u]) return 0; sz[u]=1;
      |                          ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15544 KB Output is correct
2 Correct 66 ms 16992 KB Output is correct
3 Correct 147 ms 17260 KB Output is correct
4 Correct 98 ms 17224 KB Output is correct
5 Correct 60 ms 16948 KB Output is correct
6 Correct 670 ms 17096 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15544 KB Output is correct
2 Correct 66 ms 16992 KB Output is correct
3 Correct 147 ms 17260 KB Output is correct
4 Correct 98 ms 17224 KB Output is correct
5 Correct 60 ms 16948 KB Output is correct
6 Correct 670 ms 17096 KB Output is correct
7 Correct 47 ms 15624 KB Output is correct
8 Correct 63 ms 17276 KB Output is correct
9 Correct 282 ms 17328 KB Output is correct
10 Correct 93 ms 17292 KB Output is correct
11 Correct 59 ms 17000 KB Output is correct
12 Correct 1123 ms 17196 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15592 KB Output is correct
2 Execution timed out 3544 ms 45120 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15592 KB Output is correct
2 Execution timed out 3544 ms 45120 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15476 KB Output is correct
2 Correct 313 ms 54300 KB Output is correct
3 Correct 291 ms 54312 KB Output is correct
4 Correct 279 ms 54212 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15476 KB Output is correct
2 Correct 313 ms 54300 KB Output is correct
3 Correct 291 ms 54312 KB Output is correct
4 Correct 279 ms 54212 KB Output is correct
5 Correct 43 ms 15584 KB Output is correct
6 Correct 326 ms 55260 KB Output is correct
7 Correct 302 ms 55416 KB Output is correct
8 Correct 348 ms 55700 KB Output is correct
9 Correct 332 ms 55772 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15564 KB Output is correct
2 Correct 255 ms 45472 KB Output is correct
3 Correct 256 ms 46496 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15564 KB Output is correct
2 Correct 255 ms 45472 KB Output is correct
3 Correct 256 ms 46496 KB Output is correct
4 Correct 45 ms 15528 KB Output is correct
5 Correct 275 ms 46680 KB Output is correct
6 Correct 278 ms 47000 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15520 KB Output is correct
2 Correct 299 ms 54288 KB Output is correct
3 Correct 290 ms 54340 KB Output is correct
4 Correct 287 ms 54176 KB Output is correct
5 Correct 44 ms 15556 KB Output is correct
6 Correct 258 ms 45512 KB Output is correct
7 Correct 260 ms 46276 KB Output is correct
8 Execution timed out 3564 ms 46084 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15520 KB Output is correct
2 Correct 299 ms 54288 KB Output is correct
3 Correct 290 ms 54340 KB Output is correct
4 Correct 287 ms 54176 KB Output is correct
5 Correct 44 ms 15556 KB Output is correct
6 Correct 258 ms 45512 KB Output is correct
7 Correct 260 ms 46276 KB Output is correct
8 Execution timed out 3564 ms 46084 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15572 KB Output is correct
2 Correct 64 ms 16984 KB Output is correct
3 Correct 149 ms 17200 KB Output is correct
4 Correct 96 ms 17220 KB Output is correct
5 Correct 59 ms 16840 KB Output is correct
6 Correct 674 ms 17164 KB Output is correct
7 Correct 47 ms 15552 KB Output is correct
8 Execution timed out 3582 ms 44964 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15572 KB Output is correct
2 Correct 64 ms 16984 KB Output is correct
3 Correct 149 ms 17200 KB Output is correct
4 Correct 96 ms 17220 KB Output is correct
5 Correct 59 ms 16840 KB Output is correct
6 Correct 674 ms 17164 KB Output is correct
7 Correct 47 ms 15552 KB Output is correct
8 Execution timed out 3582 ms 44964 KB Time limit exceeded
9 Halted 0 ms 0 KB -