Submission #658629

#	Time	Username	Problem	Language	Result	Execution time	Memory
658629		Lobo	Inside information (BOI21_servers)	C++17	0 / 100	17 ms	28528 KiB

servers

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int inf = 1e9+10;
const int maxn = 3e5+10;

int n, k, h[maxn];
int pp[maxn][25], pmn[maxn][25], pmx[maxn][25], pin[maxn][25], pde[maxn][25];
int dpt[maxn], dpp[maxn];
map<int,int> dp[maxn];
vector<pair<int,int>> g[maxn];

void dfs(int u, int ant) {
    for(int i = 1; i <= 20; i++) {
        if(pp[u][i-1] == -1) {
            pp[u][i] = -1;
            pmn[u][i] = pmn[u][i-1];
            pmx[u][i] = pmx[u][i-1];
            pin[u][i] = pin[u][i-1];
            pde[u][i] = pde[u][i-1];
        }
        else {
            pp[u][i] = pp[pp[u][i-1]][i-1];
            pmn[u][i] = min(pmn[u][i-1],pmn[pp[u][i-1]][i-1]);
            pmx[u][i] = max(pmx[u][i-1],pmx[pp[u][i-1]][i-1]);

            pde[u][i] = pde[u][i-1]&pde[pp[u][i-1]][i-1]&(pmn[u][i-1] > pmx[pp[u][i-1]][i-1]);
            pin[u][i] = pin[u][i-1]&pin[pp[u][i-1]][i-1]&(pmx[u][i-1] < pmn[pp[u][i-1]][i-1]);
        }
    }

    for(auto V : g[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        pmn[v][0] = w;
        pmx[v][0] = w;
        pin[v][0] = 1;
        pde[v][0] = 1;
        pp[v][0] = u;
        h[v] = h[u]+1;
        dfs(v,u);
    }
}

int lca(int u, int v) {
    if(h[v] > h[u]) {
        swap(u,v);
    }

    for(int i = 20; i >= 0; i--) {
        if(pp[u][i] != -1 && h[pp[u][i]] >= h[v]) u = pp[u][i];
    }

    if(u == v) return u;

    for(int i = 20; i >= 0; i--) {
        if(pp[u][i] != -1 && pp[v][i] != -1 && pp[u][i] != pp[v][i]) {
            u = pp[u][i];
            v = pp[v][i];
        }
    }
    return pp[u][0];
}

int qryQ(int u, int v, int w) {
    int lc = lca(u,v);
    int ans = 1;

    vector<int> ordu, ordv, ords;
    // while(u != lc) {
    //     ordu.pb(pmn[u][0]);
    //     u = pp[u][0];
    // }
    for(int i = 20; i >= 0; i--) {
        if(pp[u][i] != -1 && h[pp[u][i]] >= h[lc]) {
            if(pin[u][i] == 0) ans = 0;
            ordu.pb(pmn[u][i]);
            ordu.pb(pmx[u][i]);
            u = pp[u][i];
        }
    }

    // while(v != lc) {
    //     ordv.pb(pmn[v][0]);
    //     v = pp[v][0];
    // }
    for(int i = 20; i >= 0; i--) {
        if(pp[v][i] != -1 && h[pp[v][i]] >= h[lc]) {
            if(pde[v][i] == 0) ans = 0;
            ordv.pb(pmx[v][i]);
            ordv.pb(pmn[v][i]);
            v = pp[v][i];
        }
    }

    for(auto x : ordu) ords.pb(x);
    reverse(all(ordv));
    for(auto x : ordv) ords.pb(x);

    for(int i = 0; i < ords.size(); i++) {
        if(ords[i] > w) ans = 0;
        if(i != 0 && ords[i] < ords[i-1]) ans = 0;
    }
    return ans;
}

int szct[maxn], block[maxn], lvlct[maxn], parct[maxn];
int inc[25][maxn], dcr[25][maxn], idct[25][maxn], prevct[25][maxn], prevctw[25][maxn];
vector<int> pass, bit[maxn];
void dfsszct(int u, int ant) {
    pass.pb(u);
    szct[u] = 1;
    for(auto V : g[u]) if(!block[V.fr] && V.fr != ant) {
        int v = V.fr;
        dfsszct(v,u);
        szct[u]+= szct[v];
    }
}

void dfsct(int u, int ant, int antw, int lvlcur) {
    for(auto V : g[u]) if(!block[V.fr] && V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        inc[lvlcur][v] = inc[lvlcur][u]&(w > antw);
        dcr[lvlcur][v] = dcr[lvlcur][u]&(w < antw);
        idct[lvlcur][v] = idct[lvlcur][u];
        prevct[lvlcur][v] = u;
        prevctw[lvlcur][v] = prevctw[lvlcur][u];
        dfsct(v,u,w,lvlcur);
    }
}

int buildcentroid(int rt, int lvlcur) {
    pass.clear();
    dfsszct(rt,0);

    int ct;
    for(auto u : pass) {
        bool okct = true;
        if(szct[rt]-szct[u] > szct[rt]/2) okct = false;
        for(auto V : g[u]) if(!block[V.fr] && szct[V.fr] < szct[u]) {
            int v = V.fr;
            if(szct[v] > szct[rt]/2) okct = false;
        }

        if(okct) {
            ct = u;
            break;
        }
    }

    for(auto x : pass) {
        // cout << x << " ";
    }
    // cout << " " << ct << endl << endl;

    block[ct] = 1;
    lvlct[ct] = lvlcur;

    vector<pair<int,int>> ord;
    for(auto V : g[ct]) if(!block[V.fr]) {
        int v = V.fr;
        int w = V.sc;
        ord.pb(mp(w,v));
    }
    sort(all(ord),greater<pair<int,int>>());
    bit[ct].resize((int) ord.size()+1,0);
    idct[lvlcur][ct] = ord.size()+1;
    inc[lvlcur][ct] = 1;
    dcr[lvlcur][ct] = 1;
    prevctw[lvlcur][ct] = 0;

    for(int i = 1; i <= ord.size(); i++) {
        int v = ord[i-1].sc;
        int w = ord[i-1].fr;
        //cout << "     " << i << " " << v << " " << w << endl;
        inc[lvlcur][v] = 1;
        dcr[lvlcur][v] = 1;
        idct[lvlcur][v] = i;
        prevct[lvlcur][v] = ct;
        prevctw[lvlcur][v] = w;
        dfsct(v,0,w,lvlcur);
    }
    for(auto x : pass) {
        if(x != -1) {
            // cout << "   " << x << "  = " << idct[lvlcur][x] << " " << inc[lvlcur][x] << " " << dcr[lvlcur][x] << " " << prevct[lvlcur][x] << endl; 
        }
    }

    for(auto V : g[ct]) if(!block[V.fr]) {
        int v = V.fr;
        parct[buildcentroid(v,lvlcur+1)] = ct;
    }
    return ct;
}

void updbit(int ct, int pos, int val) {
    for(int i = pos; i < bit[ct].size(); i+= i&-i) {
        bit[ct][i]+= val;
    }
}
int qrybit(int ct, int pos) {
    int val = 0;
    for(int i = pos; i > 0; i-= i&-i) {
        val+= bit[ct][i];
    }
    return val+1;
}

int32_t main() {
    freopen("in.in", "r", stdin);
    cin >> n >> k;
    vector<pair<pair<int,int>,pair<int,int>>> qrys;
    for(int i = 1; i <= n+k-1; i++) {
        char op; cin >> op;
        if(op == 'S') {
            int u,v;cin >> u >> v;
            g[u].pb(mp(v,i));
            g[v].pb(mp(u,i));
            qrys.pb(mp(mp(0,i),mp(u,v)));
        }
        else if(op == 'Q') {
            int u,v; cin >> u >> v;
            qrys.pb(mp(mp(1,i),mp(u,v)));
        }
        else if(op == 'C') {
            int v; cin >> v;
            qrys.pb(mp(mp(2,i),mp(v,0)));
        }
    }

    buildcentroid(1,0);

    pp[1][0] = -1;
    pmn[1][0] = inf;
    pmx[1][0] = -inf;
    pin[1][0] = 1;
    pde[1][0] = 1;
    dfs(1,1);

    for(int i = 1; i <= n; i++) {
        dpt[i] = 1;
        dpp[i] = 0;
        dp[i][n+k] = 1;
    }

    for(auto X : qrys) {
        int optp = X.fr.fr;
        if(optp == 0) {
            int u = X.sc.fr;
            int v = X.sc.sc;
            if(h[v] < h[u]) swap(u,v);
            // u is parent of v

            // int p = v;
            // int antw = inf;
            // while(pp[p][0] != -1 && pmn[p][0] < antw) {
            //     antw = pmn[p][0];
            //     p = pp[p][0];
            // }

            // // p is the lowest ancestor of v that v...p is dcrreacing, so u...p can reach v

            // int x = v;
            // while(x != p) {
            //     int w1 = pmn[x][0];
            //     x = pp[x][0];
            //     dp[x][w1]+= 1;
            // }

            int ct,lvl;
            ct = v;
            lvl = lvlct[ct];
            while(lvl != -1) {
                if(prevct[lvl][v] == u) {
                    if(inc[lvl][v]) {
                        updbit(ct,idct[lvl][v],1);
                    }
                }
                ct = parct[ct];
                lvl--;
            }

            ct = u;
            lvl = lvlct[ct];
            while(lvl != -1) {
                if(prevct[lvl][u] == v) {
                    if(inc[lvl][u]) {
                        updbit(ct,idct[lvl][u],1);
                    }
                }
                ct = parct[ct];
                lvl--;
            }
            // //cout << "  " << u << " " << v << endl;
            // for(int i = 1; i <= n; i++) {
            //     //cout << i << " " << dp[i] << endl;
            // }
        }
        // if(optp == 2) {
        //     int v = X.sc.fr;
        //     int w = X.fr.sc;
        //     int ans = 0;
        //     for(int u = 1; u <= n; u++) ans+= qryQ(v,u,w);
        //     //cout << ans << endl;
        // }
        if(optp == 2) {
            int v = X.sc.fr;
            int w = X.fr.sc;

            // int p = v;
            // int antw = 0;
            // while(pp[p][0] != -1 && pmx[p][0] < w && pmn[p][0] > antw) {
            //     antw = pmn[p][0];
            //     p = pp[p][0];
            // }

            // int x = v;
            // int ans = 0;
            // antw = 0;
            // while(h[x] >= h[p] && x != -1) {
            //     for(auto it : dp[x]) {
            //         if(it.fr > antw) ans+= it.sc;
            //     }
            //     antw = pmx[x][0];
            //     x = pp[x][0];
            // }

            // // //cout << ans << endl;

            int ct,lvl;
            int ans = 0;
            ct = v;
            lvl = lvlct[v];
            while(lvl != -1) {
                if(dcr[lvl][v] && prevctw[lvl][v] <= w) {
                    ans+= qrybit(ct,idct[lvl][v]-1);

                }
                ct = parct[ct];
                lvl--;
            }
            cout << ans << endl;
        }
        if(optp == 1) {
            int w = X.fr.sc;
            int u = X.sc.sc;
            int v = X.sc.fr;
            if(qryQ(u,v,w)) cout << "yes" << endl;
            else cout << "no" << endl;
        }
    }

}

Compilation message (stderr)

servers.cpp: In function 'long long int qryQ(long long int, long long int, long long int)':
servers.cpp:106:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i = 0; i < ords.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
servers.cpp: In function 'long long int buildcentroid(long long int, long long int)':
servers.cpp:158:14: warning: unused variable 'x' [-Wunused-variable]
  158 |     for(auto x : pass) {
      |              ^
servers.cpp:179:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |     for(int i = 1; i <= ord.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
servers.cpp: In function 'void updbit(long long int, long long int, long long int)':
servers.cpp:204:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |     for(int i = pos; i < bit[ct].size(); i+= i&-i) {
      |                      ~~^~~~~~~~~~~~~~~~
servers.cpp: In function 'int32_t main()':
servers.cpp:217:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |     freopen("in.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'long long int buildcentroid(long long int, long long int)':
servers.cpp:143:9: warning: 'ct' may be used uninitialized in this function [-Wmaybe-uninitialized]
  143 |     int ct;
      |         ^~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5