Submission #549646

#	Time	Username	Problem	Language	Result	Execution time	Memory
549646		fcmalkcin	Inside information (BOI21_servers)	C++17	0 / 100	46 ms	22076 KiB

servers

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
#define pb push_back
#define F(i,a,b) for(ll i=a;i<=b;i++)

const ll maxn=2e5+10 ;
const ll base=3e18;
const ll mod= 1e9+7 ;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

/// have medal in APIO
/// goal 2/8

char p[maxn];
ll x[maxn];
ll y[maxn];
vector<pll> adj[maxn];
ll siz[maxn];
bool dd[maxn];
ll find_siz(ll u,ll par)
{
    siz[u]=1;
    for (auto p:adj[u])
    {
        ll to=p.ff;
        if (to==par||dd[to])
            continue;
        siz[u]+=find_siz(to,u);
    }
    return siz[u];
}
ll find_cen(ll u,ll par,ll siz1)
{
    ll mx=siz1-siz[u];
    for (auto p:adj[u])
    {
        ll to=p.ff;
        if (to==par||dd[to])
            continue;
        mx=max(mx,siz[to]);
        ll h=find_cen(to,u,siz1);
        if (h!=-1)
        {
            return h;
        }
    }
    if (mx*2<=siz1)
        return u;
    return -1;
}
ll fwt[maxn];
ll dd1[maxn];
vector<ll> adjq[maxn];
vector<pll> adjq1[maxn];
ll res[maxn];

bool lf(pll x,pll y)
{
    return x.ss<y.ss;
}
void update(ll x,ll diff)
{
    for (int i=x; i<maxn; i+= i&(-i))
        fwt[i]+=diff;
}
ll get(ll x,ll y)
{
    ll ans=0;
    for (int i=y; i; i-= i&(-i))
        ans+=fwt[i];
    for (int i=x-1; i; i-= i&(-i))
        ans-=fwt[i];
    return ans;
}
void dfsget(ll u,ll par,ll pre,ll mx)
{
    for (auto to:adjq1[u])
    {
        ll id=to.ss;
        ll nxt=to.ff;
        if (dd1[nxt]&&mx<id&&dd1[nxt]<=id)
        {
            res[id]=1;
        }
    }
    for (auto p:adjq[u])
    {
        if (p>=mx)
        {
            res[p]+=get(1,p);
        }
    }
    for (auto p:adj[u])
    {
        ll to=p.ff;
        ll w=p.ss;
        if (dd[to]||to==par)
            continue;
        if (w<pre)
        {
            dfsget(to,u,w,mx);
        }
    }
}
void dfsup(ll u,ll par,ll pre,ll diff,ll t)
{
    update(pre,diff);
    dd1[u]=t*pre;
    for (auto p:adj[u])
    {
        ll to=p.ff;
        ll w=p.ss;
        if (dd[to]||to==par)
            continue;
        if (w>pre)
        {
            dfsup(to,u,w,diff,t);
        }
    }
}

void centroid(ll u)
{
    ll siz=find_siz(u,0);
    sort(adj[u].begin(),adj[u].end(),lf);
    ll cen=find_cen(u,0,siz);
    update(1,1);
    dd1[cen]=1;
    // cout <<cen<<" chk1"<<endl;
    for (int i=adj[cen].size()-1; i>=0; i--)
    {
        ll to=adj[cen][i].ff;
        if (dd[to])
            continue;
        //  cout <<to<<" "<<adj[cen][i].ss<<" wtf"<<endl;
        dfsget(to,cen,adj[cen][i].ss,adj[cen][i].ss);
        dfsup(to,cen,adj[cen][i].ss,1,1);
    }
    dd1[cen]=0;
    update(1,-1);
    for (auto p:adjq[cen])
    {
        res[p]+=get(1,p);
    }
    for (int i=adj[cen].size()-1; i>=0; i--)
    {
        ll to=adj[cen][i].ff;
        if (dd[to])
            continue;
        dfsup(to,cen,adj[cen][i].ss,-1,0);
    }
    dd[cen]=1;
   // exit(0);
    for (auto p:adj[cen])
    {
        ll to=p.ff;
        if (dd[to])
            continue;
        centroid(to);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ll n, k;
    cin>> n>> k;
    k+=n-1;
    for (int i=1; i<=k; i++)
    {
        cin>> p[i];
        if (p[i]=='C')
        {
            cin>> x[i];
            adjq[x[i]].pb(i);
        }
        else
        {
            cin>> x[i]>> y[i];
            if (p[i]=='S')
            {
                adj[x[i]].pb(make_pair(y[i],i));
                adj[y[i]].pb(make_pair(x[i],i));
            }
            else
            {
                adjq1[y[i]].pb(make_pair(x[i],i));
            }
        }
    }
    centroid(1);
    for (int i=1; i<=k; i++)
    {
        if (p[i]=='C')
        {
            cout <<res[i]+1<<endl;
        }
        else if (p[i]=='Q')
        {
            if (res[i])
                cout <<"yes"<<endl;
            else
                cout <<"no"<<endl;
        }
    }
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:176:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:177:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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