Submission #818923

#	Time	Username	Problem	Language	Result	Execution time	Memory
818923		winter0101	Inside information (BOI21_servers)	C++14	100 / 100	420 ms	91168 KiB

servers

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
const int maxn=1e5+2e4+9;
struct query{
char quest;
int x,y;
}qr[maxn*2];
vector<pii>a[maxn];
int n,k;
int sub[maxn];
bool use[maxn];
void dfs(int u,int par){
sub[u]=1;
for (auto v:a[u]){
    if (v.fi==par||use[v.fi])continue;
    dfs(v.fi,u);
    sub[u]+=sub[v.fi];
}
}
int cen(int u,int par,int mx){
for(auto v:a[u]){
    if (use[v.fi]||v.fi==par)continue;
    if (sub[v.fi]*2>mx)return cen(v.fi,u,mx);
}
return u;
}
int dep[maxn],p[maxn];
pii mx[maxn][18],mn[maxn][18];
vector<int>ask[maxn];
int ans[maxn*2];
struct vertice{
int val,u,type;
bool operator < (const vertice &p1){
if (val==p1.val)return type<p1.type;
return val>p1.val;
}
};
vector<vertice>len[maxn];
void dfsmax(int u,int par,int s,int e,int root){
mx[u][dep[root]]={s,e};
if (par)len[root].pb({s,u,1});
for (auto v:a[u]){
    if (v.fi==par||use[v.fi])continue;
    int news=s,newe=e;
    if (e<=v.se)continue;
    if (s==n+k)news=v.se;
    newe=v.se;
    dfsmax(v.fi,u,news,newe,root);
}
}
void dfsmin(int u,int par,int s,int e,int root){
mn[u][dep[root]]={s,e};
if (par){
len[root].pb({s,u,2});
}
for (auto v:a[u]){
    if (v.fi==par||use[v.fi])continue;
    int news=s,newe=e;
    if (e>=v.se)continue;
    newe=v.se;
    if (s==0)news=v.se;
    dfsmin(v.fi,u,news,newe,root);
}
}
struct BIT{
vector<int>bit;
int m;
void resz(int _n){
m=_n;
bit.resize(m+1);
}
void add(int pos,int val){
//cerr<<"ADD "<<pos<<'\n';
for(;pos<=m;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
int get(int pos){
int sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
int get(int l,int r){
if (l>r)return 0;
return get(r)-get(l-1);
}
}bit;
void decompose(int u,int c){
dfs(u,0);
int newcen=cen(u,0,sub[u]);
//cerr<<newcen<<'\n';
if (c)dep[newcen]=dep[c]+1,p[newcen]=c;
dfsmax(newcen,0,n+k,n+k,newcen);
dfsmin(newcen,0,0,0,newcen);
sort(all(len[newcen]));
for (auto v:len[newcen]){
    if (v.type==2){
       //cerr<<v.u<<" "<<mx[v.u][dep[newcen]].se<<'\n';
       bit.add(mn[v.u][dep[newcen]].se,1);
    }
    else {
       for (auto v1:ask[v.u]){
        if (v.val<=v1)ans[v1]+=bit.get(v1)+1;
       }
    }
}
for (auto v:ask[newcen]){
    ans[v]+=1+bit.get(v);
}
for (auto v:len[newcen])if (v.type==2)bit.add(mn[v.u][dep[newcen]].se,-1);
use[newcen]=1;
for (auto v:a[newcen]){
    if (use[v.fi])continue;
    decompose(v.fi,newcen);
}
}
int lca(int u,int v){
if (dep[u]<dep[v])swap(u,v);
int k1=dep[u]-dep[v];
for1(i,1,k1)u=p[u];
if (u==v)return u;
while (true){
    if (u==v)return u;
    u=p[u];
    v=p[v];
}
}
void init(){
cin>>n>>k;
for1(i,1,n+k-1){
cin>>qr[i].quest;
if (qr[i].quest=='C')cin>>qr[i].x;
else cin>>qr[i].x>>qr[i].y;
if (qr[i].quest=='S'){
    a[qr[i].x].pb({qr[i].y,i});
    a[qr[i].y].pb({qr[i].x,i});
}
if (qr[i].quest=='C'){
    ask[qr[i].x].pb(i);
}
}
bit.resz(n+k);
}
bool dosmth(int u,int v,int t){
//edg tang dan tu v
int m=lca(u,v);
//cerr<<m<<'\n';
if (u==v)return 1;
if (u==m){
    if (mx[v][dep[m]].fi<=t&&mx[v][dep[m]].fi>0)return 1;
    return 0;
}
if (v==m){
    if (mn[u][dep[m]].se<=t&&mn[u][dep[m]].se>0)return 1;
    return 0;
}
if (mn[u][dep[m]].se<=0||mx[v][dep[m]].fi<=0)return 0;
if (mn[u][dep[m]].se>t)return 0;
if (mn[u][dep[m]].fi>mx[v][dep[m]].fi)return 1;
return 0;
}
void solve(){
for1(i,1,n+k-1){
if (qr[i].quest=='S')continue;
if (qr[i].quest=='Q'){
     if (dosmth(qr[i].x,qr[i].y,i))cout<<"yes"<<'\n';
     else cout<<"no"<<'\n';
}
else {
    cout<<ans[i]<<'\n';
}
}
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    init();
    decompose(1,0);
    solve();
}

• 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