oj.uz

Submission #417564

# Submission time Handle Problem Language Result Execution time Memory
417564 2021-06-04T00:33:53 Z jainbot27 Inside information (BOI21_servers) C++17
35 / 100
 3500 ms 53364 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]=(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";
    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 46 ms 14912 KB Output is correct
2 Correct 66 ms 15976 KB Output is correct
3 Correct 146 ms 16148 KB Output is correct
4 Correct 101 ms 16100 KB Output is correct
5 Correct 61 ms 15800 KB Output is correct
6 Correct 661 ms 16032 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14912 KB Output is correct
2 Correct 66 ms 15976 KB Output is correct
3 Correct 146 ms 16148 KB Output is correct
4 Correct 101 ms 16100 KB Output is correct
5 Correct 61 ms 15800 KB Output is correct
6 Correct 661 ms 16032 KB Output is correct
7 Correct 47 ms 14912 KB Output is correct
8 Correct 64 ms 16344 KB Output is correct
9 Correct 284 ms 16692 KB Output is correct
10 Correct 94 ms 16364 KB Output is correct
11 Correct 59 ms 16252 KB Output is correct
12 Correct 1126 ms 16456 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14916 KB Output is correct
2 Execution timed out 3551 ms 42504 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 14916 KB Output is correct
2 Execution timed out 3551 ms 42504 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 14928 KB Output is correct
2 Correct 330 ms 51256 KB Output is correct
3 Correct 302 ms 51268 KB Output is correct
4 Correct 290 ms 51188 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14928 KB Output is correct
2 Correct 330 ms 51256 KB Output is correct
3 Correct 302 ms 51268 KB Output is correct
4 Correct 290 ms 51188 KB Output is correct
5 Correct 44 ms 14912 KB Output is correct
6 Correct 353 ms 52552 KB Output is correct
7 Correct 323 ms 52712 KB Output is correct
8 Correct 361 ms 53364 KB Output is correct
9 Correct 386 ms 53268 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14860 KB Output is correct
2 Correct 269 ms 42552 KB Output is correct
3 Correct 281 ms 43272 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14860 KB Output is correct
2 Correct 269 ms 42552 KB Output is correct
3 Correct 281 ms 43272 KB Output is correct
4 Correct 46 ms 15004 KB Output is correct
5 Correct 282 ms 44100 KB Output is correct
6 Correct 332 ms 44272 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14936 KB Output is correct
2 Correct 325 ms 51232 KB Output is correct
3 Correct 307 ms 51232 KB Output is correct
4 Correct 301 ms 51288 KB Output is correct
5 Correct 46 ms 14836 KB Output is correct
6 Correct 264 ms 42512 KB Output is correct
7 Correct 295 ms 43416 KB Output is correct
8 Execution timed out 3579 ms 43104 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14936 KB Output is correct
2 Correct 325 ms 51232 KB Output is correct
3 Correct 307 ms 51232 KB Output is correct
4 Correct 301 ms 51288 KB Output is correct
5 Correct 46 ms 14836 KB Output is correct
6 Correct 264 ms 42512 KB Output is correct
7 Correct 295 ms 43416 KB Output is correct
8 Execution timed out 3579 ms 43104 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 14892 KB Output is correct
2 Correct 64 ms 15916 KB Output is correct
3 Correct 150 ms 16096 KB Output is correct
4 Correct 97 ms 16000 KB Output is correct
5 Correct 60 ms 15768 KB Output is correct
6 Correct 659 ms 15944 KB Output is correct
7 Correct 48 ms 14916 KB Output is correct
8 Execution timed out 3560 ms 42392 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 14892 KB Output is correct
2 Correct 64 ms 15916 KB Output is correct
3 Correct 150 ms 16096 KB Output is correct
4 Correct 97 ms 16000 KB Output is correct
5 Correct 60 ms 15768 KB Output is correct
6 Correct 659 ms 15944 KB Output is correct
7 Correct 48 ms 14916 KB Output is correct
8 Execution timed out 3560 ms 42392 KB Time limit exceeded
9 Halted 0 ms 0 KB -