Submission #1059528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059528		heeew	Telephone Plans (CCO24_day2problem3)	C++14	25 / 25	1439 ms	156864 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_set>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_N=500010;
const int MAX_Q=1500010;

struct Obj
{
    int v,p;
    unordered_set<int>::iterator it;
};

int in,n,q;
unordered_set<int> edge[MAX_N];
int cidx=0;
int cnt[MAX_N<<1];
int col[MAX_N<<1];
lint sum[MAX_Q],sump[MAX_Q];

int getmin(int x,int y)
{
    vector<Obj> vx={{x,y,edge[x].begin()}},vy={{y,x,edge[y].begin()}};
    while(1)
    {
        while(!vx.empty())
        {
            auto p=vx.back();
            if(p.it==edge[p.v].end())
            {
                vx.pop_back();
                continue;
            }
            int v=*p.it;
            vx.back().it=next(p.it);
            if(v==p.p)continue;
            vx.push_back({v,p.v,edge[v].begin()});
            break;
        }
        if(vx.empty())return x;
        while(!vy.empty())
        {
            auto p=vy.back();
            if(p.it==edge[p.v].end())
            {
                vy.pop_back();
                continue;
            }
            int v=*p.it;
            vy.back().it=next(p.it);
            if(v==p.p)continue;
            vy.push_back({v,p.v,edge[v].begin()});
            break;
        }
        if(vy.empty())return y;
    }
    return x;
}

void colorall(int v,int p,int c)
{
    cnt[col[v]]--;
    col[v]=c;
    cnt[col[v]]++;
    for(auto v0 : edge[v])
        if(v0!=p)
            colorall(v0,v,c);
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> in >> n >> q;
    for(int i=0;i<n;i++)
    {
        col[i+1]=i;
        cnt[i]=1;
    }
    cidx=n;
    lint lasta=0,change=0;
    for(int i=1;i<=q;i++)
    {
        int o;
        lint x,y,t;
        cin >> o;
        if(o==1)
        {
            cin >> x >> y;
            if(in)x^=lasta,y^=lasta;
            if(x>y)swap(x,y);
            change=(lint)cnt[col[x]]*cnt[col[y]];
            if(cnt[col[x]]<cnt[col[y]])
                colorall(x,y,col[y]);
            else
                colorall(y,x,col[x]);
            edge[x].insert(y);
            edge[y].insert(x);
        }
        if(o==2)
        {
            cin >> x >> y;
            if(in)x^=lasta,y^=lasta;
            edge[x].erase(y);
            edge[y].erase(x);
            if(getmin(x,y)==x)
                colorall(x,y,cidx++);
            else
                colorall(y,x,cidx++);
            change=-(lint)cnt[col[x]]*cnt[col[y]];
        }
        if(o==3)change=0;
        sum[i]=sum[i-1]+change;
        sump[i]=sump[i-1]+max(0LL,change);
        if(o==3)
        {
            cin >> t;
            if(in)t^=lasta;
            int j=max(0LL,i-t);
            lasta=sum[j]+sump[i]-sump[j];
            cout << lasta << '\n';
        }
    }
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 2 / 2
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5