oj.uz

Submission #1059522

# Submission time Handle Problem Language Result Execution time Memory
1059522 2024-08-15T04:32:53 Z heeew Telephone Plans (CCO24_day2problem3) C++14
0 / 25
 26 ms 65012 KB 
#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;
            }
            vx.back().it=next(p.it);
            int v=*vx.back().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;
            }
            vy.back().it=next(p.it);
            int v=*vy.back().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
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 32092 KB Output is correct
2 Correct 6 ms 32092 KB Output is correct
3 Runtime error 25 ms 64996 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 32088 KB Output is correct
2 Correct 6 ms 32092 KB Output is correct
3 Runtime error 26 ms 65012 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 32092 KB Output is correct
2 Correct 6 ms 32092 KB Output is correct
3 Runtime error 25 ms 64996 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 32088 KB Output is correct
2 Correct 6 ms 32092 KB Output is correct
3 Runtime error 26 ms 65012 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 32092 KB Output is correct
2 Correct 6 ms 32092 KB Output is correct
3 Runtime error 25 ms 64996 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 32088 KB Output is correct
2 Correct 6 ms 32092 KB Output is correct
3 Runtime error 26 ms 65012 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 32088 KB Output is correct
2 Correct 6 ms 32092 KB Output is correct
3 Runtime error 26 ms 65012 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -