Submission #402434

#	Time	Username	Problem	Language	Result	Execution time	Memory
402434		doowey	Inside information (BOI21_servers)	C++14	100 / 100	621 ms	33828 KiB

servers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 120100;
const int M = N * 2;
vector<pii> T[N];
vector<pii> qq[N];
vector<int> cc[N];
int bruh[M];
int soln[M];

bool chk(int node, int par, int target, int las){
    if(node == target) return true;
    for(auto x : T[node]){
        if(x.fi == par || x.se < las) continue;
        if(chk(x.fi, node, target, x.se))
            return true;
    }
    return false;
}

int segt[M * 2 + 512];
int lim;

vector<pii> up;

void upd(int idx, int v, bool keep){
    if(keep)up.push_back(mp(idx, v));
    idx += lim;
    while(idx > 0){
        segt[idx] += v;
        idx /= 2;
    }
}

int calc(int li, int ri){
    li += lim;
    ri += lim;
    int cum = 0;
    while(li <= ri){
        if(li % 2 == 1) cum += segt[li ++ ];
        if(ri % 2 == 0) cum += segt[ri -- ];
        li /= 2;
        ri /= 2;
    }
    return cum;
}

int sub[N];
bool vis[N];
int dd[N];
int nani[N];
int iter;

void dfs(int u, int pp){
    sub[u]=1;
    dd[u]=iter;
    nani[u]=-1;
    for(auto x : T[u]){
        if(x.fi == pp || vis[x.fi]) continue;
        dfs(x.fi, u);
        sub[u] += sub[x.fi];
    }
}

bool ton[N];
bool fron[N];
int in[N];
int shd[N];



void dfs1(int u, int pp, int ss, int l1, int l2){
    in[u]=l2;
    nani[u]=ss;
    if(l1 == -1 || l2 == -1){
        ton[u]=true;
        fron[u]=true;
    }
    else{
        if(l1 > l2){
            fron[u] = fron[pp];
            ton[u] = false;
        }
        else{
            fron[u] = false;
            ton[u] = ton[pp];
        }
    }
    for(auto x : qq[u]){
        if(dd[u]!=dd[x.fi] || nani[u]==nani[x.fi]) continue;
        if(nani[x.fi] == -1){
            soln[x.se] = -2;
        }
        else{
            if(nani[x.fi] == 0){
                if(fron[u] && shd[ss] <= x.se){
                    soln[x.se] = -1;
                }
                else{
                    soln[x.se] = -2;
                }
            }
            else{
                if(fron[u] && ton[x.fi] && in[x.fi] <= x.se){
                    soln[x.se] = -1;
                }
                else{
                    soln[x.se] = -2;
                }
            }
        }
    }
    for(auto x : cc[u]){
        if(fron[u]){
            soln[x] += calc(1, x);
            if(shd[ss] <= x)
                soln[x] ++ ;
        }
    }
    for(auto x : T[u]){
        if(x.fi == pp || vis[x.fi]) continue;
        dfs1(x.fi, u, ss, l2, x.se);
    }
    if(ton[u])
        upd(l2, +1, true);
}

bool comp(pii a, pii b){
    return a.se > b.se;
}


void decomp(int node){
    iter ++ ;
    dfs(node, -1);
    int las = -1;
    int sz = sub[node];
    bool go = true;
    while(go){
        go = false;
        for(auto x : T[node]){
            if(x.fi == las || vis[x.fi]) continue;
            if(sub[x.fi] > sz/2){
                las = node;
                node = x.fi;
                go = true;
                break;
            }
        }
    }
    fron[node]=ton[node]=true;
    nani[node] = 0;
    sort(T[node].begin(), T[node].end(), comp);
    int cv = 0;
    for(auto x : T[node]){
        if(vis[x.fi]) continue;
        cv ++ ;
        shd[cv] = x.se;
        dfs1(x.fi, node, cv, -1, x.se);
    }
    for(auto x : qq[node]){
        if(dd[node] != dd[x.fi]) continue;
        if(ton[x.fi] && in[x.fi] <= x.se){
            soln[x.se] = -1;
        }
        else{
            soln[x.se] = -2;
        }
    }
    for(auto x : cc[node]){
        soln[x] ++ ; // itself
        soln[x] += calc(1, x);

    }
    for(auto q : up){
        upd(q.fi, -q.se, false);
    }
    up.clear();

    vis[node]=true;

    for(auto x : T[node]){
        if(!vis[x.fi]) decomp(x.fi);
    }

}

int main(){
    fastIO;
    int n, q;
    cin >> n >> q;
    char typ;
    int xx, yy;
    bool sol;
    for(int iq = 1; iq <= n + q - 1; iq ++ ){
        cin >> typ;
        if(typ == 'S'){
            cin >> xx >> yy;
            T[xx].push_back(mp(yy, iq));
            T[yy].push_back(mp(xx, iq));
        }
        else if(typ == 'Q'){
            cin >> xx >> yy;
            /*
            sol = chk(yy, -1, xx, 0);
            if(sol == true){
                bruh[iq] = -1;
            }
            else{
                bruh[iq] = -2;
            }
            */
            if(xx == yy)
                soln[iq] = -1;
            else
                qq[yy].push_back(mp(xx, iq));
        }
        else{
            cin >> xx;
            cc[xx].push_back(iq);
        }
    }
    lim = n + q;
    decomp(1);
    for(int i = 1; i <= n + q - 1; i ++ ){
        if(soln[i] == 0) continue;
        if(soln[i] == -1){
            cout << "yes\n";
        }
        else if(soln[i] == -2){
            cout << "no\n";
        }
        else{
            cout << soln[i] << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:204:10: warning: unused variable 'sol' [-Wunused-variable]
  204 |     bool sol;
      |          ^~~

• 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