Submission #1150385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150385		byunjaewoo	Inside information (BOI21_servers)	C++20	100 / 100	1782 ms	208276 KiB

servers

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

const int N=240010, L=20, INF=1e9;
int n, q, siz[N], lev[N], cdep[N], cpar[N], pw[L][N], up[L][N], down[L][N], idx[L][N];
int ans[N];
vector<int> vec[N];
vector<vector<int>> vec2[N];
vector<array<int, 3>> vd[N];
bool chk[N];
vector<pair<int, int>> adj[N];
array<int, 3> r[N];

int dfs_s(int curr, int prev) {
    siz[curr]=1;
    for(auto [next, w]:adj[curr]) if(next!=prev && !chk[next]) siz[curr]+=dfs_s(next, curr);
    return siz[curr];
}

int dfs_c(int curr, int prev, int sz) {
    for(auto [next, w]:adj[curr]) if(next!=prev && !chk[next] && siz[next]>sz/2) return dfs_c(next, curr, sz);
    return curr;
}

void dfs_d(int curr, int prev, int lv, int u, int d, int uw, int cent, int k) {
    idx[lv][curr]=k;
    if(u!=-INF) up[lv][curr]=uw;
    else up[lv][curr]=INF;
    if(d!=INF) down[lv][curr]=uw, vd[d].push_back({cent, k, uw});
    else down[lv][curr]=-INF;
    for(auto [next, w]:adj[curr]) if(next!=prev && !chk[next]) {
        pw[lv][next]=w;
        dfs_d(next, curr, lv, (u>w)?w:-INF, (d<w)?w:INF, uw, cent, k);
    }
}

int dnc(int curr, int lv) {
    int sz=dfs_s(curr, 0), cent=dfs_c(curr, 0, sz);
    chk[cent]=true, lev[cent]=lv;
    up[lv][cent]=-INF, down[lv][cent]=INF, idx[lv][cent]=-1, vd[0].push_back({cent, -1, INF});
    int p=0;
    for(auto [next, w]:adj[cent]) if(!chk[next]) pw[lv][next]=w, dfs_d(next, 0, lv, w, w, w, cent, p++);
    vec2[cent].resize(p);
    for(auto [next, w]:adj[cent]) if(!chk[next]) cpar[dnc(next, lv+1)]=cent;
    return cent;
}

void dnc2(int s, int e) {
    if(s>=e) return;
    int m=(s+e)/2;
    vector<int> t;
    vector<pair<int, int>> t2;
    for(int i=s; i<=m; i++) {
        for(auto [cent, k, uw]:vd[i]) {
            vec[cent].push_back(uw);
            t.push_back(cent);
            if(k>=0) vec2[cent][k].push_back(uw), t2.push_back({cent, k});
        }
    }
    sort(t.begin(), t.end()), t.erase(unique(t.begin(), t.end()), t.end());
    sort(t2.begin(), t2.end()), t2.erase(unique(t2.begin(), t2.end()), t2.end());
    for(int i:t) sort(vec[i].begin(), vec[i].end());
    for(auto [i, j]:t2) sort(vec2[i][j].begin(), vec2[i][j].end());
    for(int i=m+1; i<=e; i++) if(r[i][0]==3) {
        int u=r[i][1];
        for(int j=u; j; j=cpar[j]) if(up[lev[j]][u]<=i) {
            int tmp=ans[i];
            ans[i]+=vec[j].end()-upper_bound(vec[j].begin(), vec[j].end(), up[lev[j]][u]);
            if(j!=u) ans[i]-=vec2[j][idx[lev[j]][u]].end()-upper_bound(vec2[j][idx[lev[j]][u]].begin(), vec2[j][idx[lev[j]][u]].end(), up[lev[j]][u]);
        }
    }
    for(int i:t) vec[i].clear();
    for(auto [i, j]:t2) vec2[i][j].clear();
    dnc2(s, m), dnc2(m+1, e);
}

int lca(int u, int v) {
    if(lev[u]<lev[v]) swap(u, v);
    while(lev[u]>lev[v]) u=cpar[u];
    while(u!=v) u=cpar[u], v=cpar[v];
    return u;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    q+=n-1;
    for(int i=1; i<=q; i++) {
        char op; cin>>op;
        if(op=='S') {
            int u, v; cin>>u>>v;
            adj[u].push_back({v, i}), adj[v].push_back({u, i});
            r[i]={1, u, v};
        }
        else if(op=='Q') {
            int u, v; cin>>u>>v;
            r[i]={2, v, u};
        }
        else {
            int u; cin>>u;
            r[i]={3, u, 0};
        }
    }
    dnc(1, 0);
    for(int i=1; i<=q; i++) if(r[i][0]==2) {
        int u=r[i][1], v=r[i][2], l=lca(u, v);
        ans[i]=(up[lev[l]][u]<down[lev[l]][v]);
        // cout<<u<<", "<<v<<": "<<l<<"\n";
        // cout<<up[lev[l]][u]<<", "<<pw[lev[l]][v]<<"\n";
        if(v==l && up[lev[l]][u]>i) ans[i]=false;
        if(v!=l && pw[lev[l]][v]>i) ans[i]=false;
        // cout<<ans[i]<<"\n";
    }
    dnc2(0, q);
    for(int i=1; i<=q; i++) {
        if(r[i][0]==2) {
            if(ans[i]) cout<<"yes\n";
            else cout<<"no\n";
        }
        else if(r[i][0]==3) cout<<ans[i]<<"\n";
    }
    return 0;
}

• Subtask 1-1: 2 / 2
• Subtask 1-2: 3 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 3 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 5 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 13 / 13
• Subtask 6-1: 17 / 17
• Subtask 6-2: 18 / 18