Submission #1059511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059511		heeew	Telephone Plans (CCO24_day2problem3)	C++14	25 / 25	3053 ms	198176 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
 
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,i;
};
 
int in,n,q;
int esz[MAX_N];
vint edge[MAX_N];
vint nxt[MAX_N];
vint ec[MAX_N];
map<pii,pii> mp;
int cidx=0;
int cnt[MAX_N<<1];
int col[MAX_N<<1];
lint sum[MAX_Q],sump[MAX_Q];
 
int rnxt(int v,int i)
{
    if(i==esz[v] || ec[v][i]==1)return i;
    return nxt[v][i]=rnxt(v,nxt[v][i]);
}
 
int getmin(int x,int y)
{
    vector<Obj> vx={{x,y,rnxt(x,0)}},vy={{y,x,rnxt(y,0)}};
    while(1)
    {
        while(!vx.empty())
        {
            auto p=vx.back();
            vx.pop_back();
            if(p.i==esz[p.v])continue;
            int v=edge[p.v][p.i];
            p.i=rnxt(p.v,nxt[p.v][p.i]);
            vx.push_back(p);
            if(v==p.p)continue;
            vx.push_back({v,p.v,rnxt(v,0)});
            break;
        }
        if(vx.empty())return x;
        while(!vy.empty())
        {
            auto p=vy.back();
            vy.pop_back();
            if(p.i==esz[p.v])continue;
            int v=edge[p.v][p.i];
            p.i=rnxt(p.v,nxt[p.v][p.i]);
            vy.push_back(p);
            if(v==p.p)continue;
            vy.push_back({v,p.v,rnxt(v,0)});
            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(int i=rnxt(v,0);i<esz[v];i=rnxt(v,nxt[v][i]))
        if(edge[v][i]!=p)
            colorall(edge[v][i],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]);
            int j=esz[x]++,l=esz[y]++;
            edge[x].push_back(y);
            nxt[x].push_back(j+1);
            ec[x].push_back(1);
            edge[y].push_back(x);
            nxt[y].push_back(l+1);
            ec[y].push_back(1);
            mp[{x,y}]={j,l};
        }
        if(o==2)
        {
            cin >> x >> y;
            if(in)x^=lasta,y^=lasta;
            if(x>y)swap(x,y);
            pii idx=mp[{x,y}];
            ec[x][idx.first]=0;
            ec[y][idx.second]=0;
            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