Submission #1115226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115226		HoriaHaivas	Inside information (BOI21_servers)	C++14	100 / 100	845 ms	56864 KiB

servers

/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    "linistiti va putin"
    - 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

struct operatie
{
    char type;
    int u;
    int v;
    int moment;
    int ans;
};

struct idk
{
    int type;///0 - update, 1 - query
    int l;
    int r;
    int who;
};

bool cmp(idk a, idk b)
{
    if (a.l!=b.l)
        return a.l>b.l;
    else
        return a.type<b.type;
}

struct edge
{
    int to;
    int w;
};

vector<idk> events;
operatie q[240005];
vector<operatie> qq[120005];
map<int,pair<int,int>> cresc;
map<int,pair<int,int>> desc;
int aib[240005];
vector<edge> nodes[120005];
bool blocked[120005];
int sz[120005];
int maxx;

void update(int idx, int delta)
{
    while (idx<=maxx)
    {
        aib[idx]+=delta;
        idx+=idx&(-idx);
    }
}

int query(int idx)
{
    int ans;
    ans=0;
    while (idx>0)
    {
        ans+=aib[idx];
        idx-=idx&(-idx);
    }
    return ans;
}

void recalc(int node, int parent)
{
    sz[node]=1;
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
        {
            recalc(x.to,node);
            sz[node]+=sz[x.to];
        }
    }
}

int find_centroid(int node, int parent, int compsize)
{
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && sz[x.to]>compsize/2)
        {
            return find_centroid(x.to,node,compsize);
        }
    }
    return node;
}

bool canadd;

void add_cresc(int node, int parent, int first, int last)
{
    cresc[node]= {first,last};
    if (canadd)
        events.push_back({0,first,last,0});
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && x.w>last)
        {
            add_cresc(x.to,node,first,x.w);
        }
    }
}

void rem_cresc(int node, int parent, int first, int last)
{
    cresc[node]= {-1,-1};
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && x.w>last)
        {
            rem_cresc(x.to,node,first,x.w);
        }
    }
}

int globc;

void solve(int node, int parent, int first, int last)
{
    desc[node]={first,last};
    for (auto x : qq[node])
    {
        if (x.type=='Q')
        {
            if (x.u==x.v)
                q[x.moment].ans|=1;
            else if (x.u==globc && first<x.moment)
                q[x.moment].ans|=1;
            else if (cresc.find(x.u)==cresc.end() || (cresc[x.u].first==-1 && cresc[x.u].second==-1))
                q[x.moment].ans|=0;
            else if (cresc[x.u].first>first && cresc[x.u].second<x.moment)
                q[x.moment].ans|=1;
        }
        else
        {
            events.push_back({1,first+1,x.moment-1,x.moment});
        }
    }
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && x.w<last)
        {
            solve(x.to,node,first,x.w);
        }
    }
}

void cd(int node)
{
    int centroid;
    cresc.clear();
    desc.clear();
    events.clear();
    recalc(node,-1);
    centroid=find_centroid(node,-1,sz[node]);
    globc=centroid;
    blocked[centroid]=1;
    canadd=1;
    for (auto x : nodes[centroid])
    {
        if (!blocked[x.to])
        {
            add_cresc(x.to,centroid,x.w,x.w);
        }
    }
    for (auto x : qq[centroid])
    {
        if (x.type=='Q')
        {
            if (x.u==x.v)
                q[x.moment].ans|=1;
            else if (cresc.find(x.u)==cresc.end() || (cresc[x.u].first==-1 && cresc[x.u].second==-1))
                q[x.moment].ans|=0;
            else if (cresc[x.u].second<x.moment)
                q[x.moment].ans|=1;
        }
        else
        {
            events.push_back({1,1,x.moment-1,x.moment});
        }
    }
    canadd=0;
    for (auto x : nodes[centroid])
    {
        if (!blocked[x.to])
        {
            rem_cresc(x.to,centroid,x.w,x.w);
            solve(x.to,centroid,x.w,x.w);
            add_cresc(x.to,centroid,x.w,x.w);
        }
    }
    sort(events.begin(),events.end(),cmp);
    for (auto x : events)
    {
        if (x.type==0)
        {
            update(x.r,1);
        }
        else
        {
            if (desc.find(q[x.who].u)==desc.end())
                q[x.who].ans+=0;
            else if (desc[q[x.who].u].first<=x.r)
                q[x.who].ans+=1;
            q[x.who].ans+=query(x.r);
        }
    }
    for (auto x : events)
    {
        if (x.type==0)
        {
            update(x.r,-1);
        }
    }
    for (auto x : nodes[centroid])
    {
        if (!blocked[x.to])
        {
            cd(x.to);
        }
    }
}

signed main()
{
    /*
    ifstream fin("secvp.in");
    ofstream fout("secvp.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k,i,j;
    cin >> n >> k;
    for (i=1; i<=n+k-1; i++)
    {
        cin >> q[i].type;
        q[i].moment=i;
        if (q[i].type=='S')
        {
            cin >> q[i].u >> q[i].v;
            nodes[q[i].u].push_back({q[i].v,i});
            nodes[q[i].v].push_back({q[i].u,i});
        }
        if (q[i].type=='Q')
        {
            cin >> q[i].u >> q[i].v;
            qq[q[i].v].push_back(q[i]);
        }
        if (q[i].type=='C')
        {
            cin >> q[i].u;
            q[i].ans=1;
            qq[q[i].u].push_back(q[i]);
        }
    }
    maxx=n+k-1;
    cd(1);
    for (i=1; i<=n+k-1; i++)
    {
        if (q[i].type=='Q')
        {
            if (q[i].ans==1)
                cout << "yes\n";
            else
                cout << "no\n";
        }
        else if (q[i].type=='C')
        {
            cout << q[i].ans << "\n";
        }
    }
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:247:15: warning: unused variable 'j' [-Wunused-variable]
  247 |     int n,k,i,j;
      |               ^

• 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