제출 #1001247

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001247		amine_aroua	Inside information (BOI21_servers)	C++17	0 / 100	159 ms	58832 KiB

servers

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int MAXN=2e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
bool removed[MAXN];
int join[20][MAXN];
vector<pair<int,int>> cnt[MAXN];
vector<pair<int,int>> adj[MAXN];
int sz[MAXN];
int up[20][MAXN];
int parent[20][MAXN];
int get_sz(int x,int p){
    sz[x]=1;
    for(auto u:adj[x]){
        if(removed[u.fi]||u.fi==p) continue;
        sz[x]+=get_sz(u.fi,x);
    }
    return sz[x];
}
int get_centroid(int x,int t_sz,int p){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        if(sz[u.fi]*2>t_sz) return get_centroid(u.fi,t_sz,x);
    }
    return x;
}
vector<bool> incre(MAXN);
vector<bool> decre(MAXN);
int cur;
void dfs(int x,int p,int edgep,int centroid,int lvl,int edge){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        decre[u.fi]=decre[x];
        incre[u.fi]=incre[x];
        if(edgep<u.se) incre[u.fi]=false;
        if(edgep>u.se) decre[u.fi]=false;
        dfs(u.fi,x,u.se,centroid,lvl,edge);
    }
    cur++;
    if(incre[x]) join[lvl][x]=edge;
    if(decre[x]) up[lvl][x] = edgep;
    parent[lvl][x] = centroid;
}
void build(int x,int lvl){
    int centroid=get_centroid(x,get_sz(x,-1),-1);
    parent[lvl][centroid]=centroid;
    join[lvl][centroid] = -1;
    up[lvl][centroid] = 1e9;
    incre[centroid]=true;
    decre[centroid]=true;
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        cur=0;
        incre[u.fi] = true;
        decre[u.fi] = true;
        dfs(u.fi,x,u.se,centroid,lvl,u.se);
        cnt[centroid].pb({u.se,cur});
    }
    removed[centroid]=true;
    for(auto u : adj[centroid]){
        if(removed[u.fi]) continue;
        build(u.fi,lvl+1);
    }
}
bool query(int x,int y,int t)
{
    bool test=false;
    for(int lvl = 0 ; lvl < 20 ; lvl++)
    {
        if(parent[lvl][x]!=parent[lvl][y]) break;
        int centroid = parent[lvl][x];
        if(centroid == -1)
            continue;
        int edgep = up[lvl][x];
        test|= ((edgep < t) || (x == centroid)) && (join[lvl][y]<edgep);
    }
    return test;
}
int main(){
    int n,k;
    cin>>n>>k;
    memset(parent,-1,sizeof parent);
    for(int i=0;i<20;i++){
        for(int j=0;j<n;j++){
            join[i][j]=1e9;
            up[i][j]=1e9;
        }
    }
    vector<pair<char , pair<int,int>>> queries;
    for(int i = 0 ; i < n - 1 + k ; i++)
    {
        char c;
        cin>>c;
        if(c == 'S')
        {
            int a , b;
            cin>>a>>b;
            a-- , b--;
            adj[a].pb({b , i});
            adj[b].pb({a , i});
            queries.pb({c , {a , b}});
        }
        else if(c == 'Q')
        {
            int a , d;
            cin>>a>>d;
            a-- , d--;
            queries.pb({c , {a , d}});
        }else{
            int a;
            cin>>a;
            a--;
            queries.pb({c , {a , -1}});
        }
    }
    build(0,0);
    for(int i = 0 ; i < n - 1 + k ; i++)
    {
        auto Cur = queries[i];
        if(Cur.fi=='Q'){
            cout << ( query(Cur.se.fi , Cur.se.se , i) ? "yes" : "no") <<endl;
        }else if(Cur.fi=='C') cout << 0 <<endl;
        // if(cur.fi == 'C')
        // {

        // }
    }
}

• 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