Submission #1235258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235258		SSSM	Inside information (BOI21_servers)	C++20	0 / 100	24 ms	24760 KiB

servers

#include <bits/stdc++.h>

/*
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx2")
*/

using namespace std;

/*
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define F first
#define S second
#define pb push_back
#define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
#define md(a) ((a%mod+mod)%mod)
#define all(a) a.begin(), a.end()
#define MP make_pair
#define lc (id<<1)
#define rc (lc|1)
#define mid (l+r)/2
#define kill(a) cout << a << "\n", exit(0)
#define SZ(a) (ll)a.size()
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
mt19937_64  rng(chrono::steady_clock::now().time_since_epoch().count());

ll const maxn=3e5+10, mod=1e9+7, INF=1e18, LOG=20, sq=65;

ll poww(ll a, ll b, ll mod) {
 if (b == 0) return 1;
 return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod;
}

int n, k, fen[maxn], ans[maxn], sz[maxn], a[maxn], qt[maxn];
vector<pii> Q[maxn], g[maxn];
vector<int> QC[maxn], V, vec;
bool hide[maxn], mark[maxn], fl[2][maxn];

void Plant(int v, int p=0)
{
    sz[v]=1;
    for(auto [u, id]:g[v])
        if(!hide[u] && u!=p) Plant(u, v), sz[v]+=sz[u]; 
}

int Find_Centroid(int v, int s, int p=0)
{
    for(auto [u, id]:g[v])
        if(!hide[u] && u!=p && s<sz[u]*2) return Find_Centroid(u, s, v);
    return v;
}

void Upd(int i, int v)
{
    for(i+=5;i<maxn;i+=(-i)&i) fen[i]+=v;   
}

int Get(int i)
{
    int s=0;
    for(i+=5;i;i-=(-i)&i) s+=fen[i];
    return s;
}

void DFS(int v, int p)
{
    fl[0][v]=fl[0][p];
    if(!hide[p]) fl[0][v]&=(a[v]<a[p]);
    fl[1][v]=fl[1][p];
    if(!hide[p]) fl[1][v]&=(a[v]>a[p]);
    vec.pb(v);
    for(auto [u, id]:g[v]) if(!hide[u] && u!=p) a[u]=id, DFS(u, v);
}

void Solve(int v)
{
    Plant(v);
    v=Find_Centroid(v, sz[v]);
    mark[v]=hide[v]=fl[0][v]=fl[1][v]=1;
    sort(all(g[v]), [&](pii x, pii y){return x.S>y.S;});
    a[v]=0;
    Upd(0, 1);
    V.clear();
    V.pb(v);
    for(auto [u, w]:g[v]){
        if(hide[u]) continue;
        vec.clear();
        a[u]=w; DFS(u, v);
        for(int x:vec){
            V.pb(x);
            for(auto [y, t]:Q[x])
                if(mark[y])
                    if(fl[1][y] && fl[0][x] && a[y]<=t) ans[t]=1;  
            for(int t:QC[x]){
                if(fl[0][x] && t>=w){
                    ans[t]+=Get(t);
                }
            }
        }
        for(int x:vec) if(fl[1][x]) Upd(a[x], 1), mark[x]=1;
    }
    for(auto [y, t]:Q[v])
        if(mark[y])
            if(fl[1][y] && a[y]<=t) ans[t]=1;  
    for(int t:QC[v]) {
        ans[t]+=Get(t);
    }
    for(int x:V) if(fl[1][x]) Upd(a[x], -1), mark[x]=0;
    for(auto [u, id]:g[v]) if(!hide[u]) Solve(u);
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>n>>k;
    for(int i=1;i<n+k;i++)
    {
        char c;
        int x, y;
        cin>>c;
        if(c=='S'){
            cin>>x>>y;
            g[x].pb({y, i});
            g[y].pb({x, i});
        }
        else if(c=='Q'){
            cin>>x>>y;
            Q[y].pb({x, i});
            qt[i]=1;
        }
        else{
            cin>>x;
            QC[x].pb(i);
            qt[i]=2;
        }
    }
    Solve(1);
    for(int i=1;i<n+k;i++)
    {
        if(qt[i]==2) cout<<ans[i]<<"\n";
        else if(qt[i]==1){
            if(ans[i]) cout<<"yes\n";
            else cout<<"no\n";
        }
    }
    return 0;
}

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