Submission #1188549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188549		DanielPr8	Inside information (BOI21_servers)	C++20	24 / 100	3597 ms	67792 KiB

servers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
vvl pr;
vvp g;
vll dep, ln;
vector<map<ll, ll>> eac;
void dfs(ll cr){
    for(pll i:g[cr]){
        if(i.f!=pr[0][cr]){
            pr[0][i.f]=cr;
            dep[i.f] = dep[cr]+1;
            ln[i.f]=i.s;
            dfs(i.f);
        }
    }
}
ll get_pr(ll i, ll j){
    for(ll h = 19; h >= 0; --h){
        if(j>=(1<<h)){
            i=pr[h][i];
            j-=(1<<h);
        }
    }
    return i;
}
ll lca(ll a, ll b){
    if(dep[a]<dep[b])swap(a, b);
    a = get_pr(a, dep[a]-dep[b]);
    if(a==b)return a;
    for(ll h = 19; h >= 0; --h){
        if(pr[h][a]!=pr[h][b]){
            a=pr[h][a];
            b=pr[h][b];
        }
    }
    return pr[0][a];
}
ll kes(ll a, ll b){
    b = get_pr(b, dep[b]-dep[a]-1);
    return ln[b];
}
vpl up, dow;
ll t = 0;
pll get_up(ll a, ll b=-1){
    if(up[a].f==a)return {a,b};
    if(ln[a]>b)return up[a] = get_up(up[a].f, up[a].s);
    return {a,b};
}
pll get_dow(ll a, ll b=1e9){
    if(dow[a].f==a)return {a,b};
    if(ln[a]<b)return dow[a] = get_dow(dow[a].f, dow[a].s);
    return {a,b};
}
void upd(ll a){
    if(a==0)return;
    eac[pr[0][a]][a]=0;
    if(ln[a]<=t)eac[pr[0][a]][a]++;
    for(pll i:g[a]){
        if(i.f==pr[0][a])continue;
        if(i.s>ln[a] && i.s<=t){
            eac[pr[0][a]][a] += eac[a][i.f];
        }
    }
    upd(pr[0][a]);
}
ll query(ll a, ll b=-1){
    ll ans=1;
    for(pll i:g[a]){
        if(i.f==pr[0][a])continue;
        if(i.s>b)ans+=eac[a][i.f];
    }
    if(a!=0 && ln[a]>b && ln[a]<=t)ans += query(pr[0][a], ln[a]);
    return ans;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll n, a, b, k;
    cin >> n >> k;
    pr = vvl(20, vll(n));
    g = vvp(n);
    ln = dep = vll(n);
    eac = vector<map<ll,ll>>(n);
    vector<pair<char, pll>> que(n+k-1);
    for(ll i = 0; i < n+k-1; ++i){
        cin >> que[i].f;
        if(que[i].f=='S'){
            cin >> que[i].s.f >> que[i].s.s;
            que[i].s.f--; que[i].s.s--;
            g[que[i].s.f].pb({que[i].s.s, i});
            g[que[i].s.s].pb({que[i].s.f, i});
        }
        else if(que[i].f=='Q'){
            cin >> que[i].s.f >> que[i].s.s;
            que[i].s.f--; que[i].s.s--;
        }
        else {cin >> que[i].s.f;que[i].s.f--;}

    }
    dfs(0);
    for(ll i = 1; i < 20; ++i){
        for(ll j = 0; j < n; ++j){
            pr[i][j] = pr[i-1][pr[i-1][j]];
        }
    }
    up = dow = vpl(n);
    for(ll i = 0; i < n; ++i){up[i]={i,-1};dow[i]={i, 1e9};}
    for(; t < n+k-1; ++t){
        if(que[t].f=='Q'){
            a = que[t].s.f;
            b = que[t].s.s;
            ll q = lca(a,b);
            if(dep[get_up(b).f]>dep[q] || dep[get_dow(a).f]>dep[q]){
                cout << "no\n";
            }
            else if((kes(q, a) < kes(q,b)) && a!=q && b!=q)cout << "no\n";
            else cout << "yes\n";
        }
        else if(que[t].f=='S'){
            a = que[t].s.f;
            b = que[t].s.s;
            if(a!=pr[0][b])swap(a,b);
            dow[b] = up[b] = {a,ln[b]};
            upd(b);
        }
        else{
            a = que[t].s.f;
            cout << query(a) << "\n";
        }
    }

    
}

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