Submission #528807

#	Time	Username	Problem	Language	Result	Execution time	Memory
528807		radal	Inside information (BOI21_servers)	C++14	100 / 100	607 ms	41232 KiB

servers

#include <bits/stdc++.h>
#define rep(i,l,r) for (int i = l; i < r; i++)
#define X first
#define Y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
constexpr int N = 3e5+20,mod = 998244353,inf = 1e9+10;
vector<pll> adj[N],Q1[N];
vector<int> Q2[N];
int sz[N],n,k,fen[N],ans[N],ch[N],W[N],lst[N];
bool hide[N],fl[N][2];
char c[N];
int siz(int v,int p){
    sz[v] = 1;
    for (pll u : adj[v]){
        if (hide[u.X] || u.X == p) continue;
        sz[v] += siz(u.X,v);
    }
    return sz[v];
}
inline void upd(int l,int x){
    for(; l < k; l |= (l+1))
        fen[l] += x;
}
inline int que(int r){
    int res = 0;
    for(; r >= 0; r = (r&(r+1))-1)
        res += fen[r];
    return res;
}
inline int cent(int v,int _n){
    int p = -1;
    while (true){
        bool f = 0;
        for (pll u : adj[v]){
            if (u.X == p || hide[u.X]) continue;
            if (sz[u.X]*2 > _n){
                p = v;
                v = u.X;
                f = 1;
                break;
            }
        }
        if (!f) break;
    }
    return v;
}
void dfs(int v,int w,int par){
    if (par == -1) fl[v][0] = fl[v][1] = 1;
    W[v] = w;
    for (pll p : adj[v]){
        int u = p.X;
        if (u == par || hide[u]) continue;
        if (par == -1){
            fl[u][0] = 1;
            fl[u][1] = 1;
            lst[u] = p.Y;
        }
        else{
            if (fl[v][0] && p.Y < w) fl[u][0] = 1;
            else fl[u][0] = 0;
            if (fl[v][1] && p.Y > w) fl[u][1] = 1;
            else fl[u][1] = 0;
            lst[u] = lst[v];
        }
        dfs(u,p.Y,v);
    }
}
void add(int v,int x,int p){
    if (!fl[v][1]) return;
    upd(W[v],x);
    ch[v] += x;
    for (pll u : adj[v]){
        if (u.X != p && !hide[u.X]){
            add(u.X,x,v);
        }
    }
}
void calc(int v,int p){
    if (!fl[v][0]) return;
    for(int t : Q2[v])
        ans[t] += que(t)+(lst[v] < t);
    for (pll u : Q1[v])
        if (u.X == v || (ch[u.X] && max(W[u.X],lst[v]) <= u.Y)) ans[u.Y] = 1;
    for (pll u : adj[v]){
        if (hide[u.X] || u.X == p) continue;
        calc(u.X,v);
    }
}
void decom(int v){
    v = cent(v,siz(v,-1));
    hide[v] = 1;
    ch[v] = 1;
    dfs(v,0,-1);
    for (pll u : adj[v]){
        if (hide[u.X]) continue;
        calc(u.X,v);
        add(u.X,1,v);
    }
    for (int t : Q2[v])
        ans[t] += que(t)+1;
    ch[v] = 0;
    for (pll u : Q1[v])
        if (u.X == v || (ch[u.X] && W[u.X] <= u.Y)) ans[u.Y] = 1;
    for (pll u : adj[v])
        if (!hide[u.X])
            add(u.X,-1,v);
    for (pll u : adj[v]) if (!hide[u.X]) decom(u.X);
}
int main(){
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    k += n;
    rep(i,1,k){
        int v;
        cin >> c[i] >> v;
        if (c[i] == 'S'){
            int u;
            cin >> u;
            adj[u].pb({v,i});
            adj[v].pb({u,i});
        }
        if (c[i] == 'Q'){
            int u;
            cin >> u;
            Q1[u].pb({v,i});
        }
        if (c[i] == 'C')
            Q2[v].pb(i);
    }
    rep(i,1,n+1) reverse(adj[i].begin(),adj[i].end());
    decom(1);
    rep(i,1,k){
        if (c[i] == 'S') continue;
        if (c[i] == 'Q')
            cout << ((ans[i]) ? "yes" : "no" ) << endl;
        else
            cout << ans[i] << endl;
    }
	return 0;
}

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