oj.uz

Submission #596096

# Submission time Handle Problem Language Result Execution time Memory
596096 2022-07-14T11:12:25 Z Bench0310 Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 67180 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=1000000;
int n;
vector<int> v[N];
int deg[N];
int bad=0;
int big[N]; //number of adjacent big nodes
int cnt[N+1]; //number of good nodes with i adjacent big nodes
int cntbad[N+1]; //number of bad nodes with i adjacent big nodes
vector<int> four;
int p[N];
int sz[N];
vector<array<int,2>> cycle_edges;
int incycle[N];
bool valid[N];

int find_set(int a)
{
    if(a==p[a]) return a;
    else return p[a]=find_set(p[a]);
}

bool merge_sets(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    if(a==b) return 0;
    if(sz[a]<sz[b]) swap(a,b);
    p[b]=a;
    sz[a]+=sz[b];
    return 1;
}

vector<int> find_path(int a,int b)
{
    vector<int> u(n,-1);
    u[a]=-2;
    queue<int> q;
    q.push(a);
    while(!q.empty())
    {
        int e=q.front();
        q.pop();
        for(int to:v[e])
        {
            if(u[to]==-1)
            {
                u[to]=e;
                q.push(to);
            }
        }
    }
    vector<int> path={b};
    while(path.back()!=a) path.push_back(u[path.back()]);
    for(int x:path) incycle[x]++;
    return path;
}

void Init(int _n)
{
    n=_n;
    cnt[0]=n;
    for(int i=0;i<n;i++)
    {
        p[i]=i;
        sz[i]=1;
        valid[i]=1;
    }
}

void upd(int a,int d)
{
    if(valid[a]) (deg[a]<=2?cnt[big[a]]:cntbad[big[a]])+=d;
}

void updbig(int a)
{
    upd(a,-1);
    big[a]++;
    upd(a,1);
}

void upddeg(int a)
{
    upd(a,-1);
    deg[a]++;
    upd(a,1);
    if(deg[a]==3)
    {
        bad++;
        for(int to:v[a]) updbig(to);
    }
    if(deg[a]==4) four.push_back(a);
}

void new_valid(vector<int> opt)
{
    vector<int> now(n,0);
    for(int a:opt) now[a]=1;
    for(int i=0;i<n;i++)
    {
        if(valid[i]&&!now[i])
        {
            upd(i,-1);
            valid[i]=0;
        }
    }
}

void Link(int a, int b)
{
    if(merge_sets(a,b)==1)
    {
        v[a].push_back(b);
        v[b].push_back(a);
    }
    else
    {
        cycle_edges.push_back({a,b});
        if(cycle_edges.size()==1) new_valid(find_path(a,b));
        else if(cycle_edges.size()==2)
        {
            vector<int> path=find_path(a,b);
            vector<int> opt;
            for(int x:path)
            {
                int c=0;
                for(int to:v[x]) c+=(incycle[to]==2);
                if(incycle[x]==2&&c<=1) opt.push_back(x);
            }
            new_valid(opt);
        }
        else new_valid({});
    }
    upddeg(a);
    upddeg(b);
}

int CountCritical()
{
    if(four.size()==0) return cnt[bad]+cntbad[bad-1];
    else if(four.size()==1) return (valid[four[0]]&&big[four[0]]==bad-1);
    else return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 17 ms 24020 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 14 ms 23908 KB Output is correct
5 Correct 13 ms 23940 KB Output is correct
6 Correct 14 ms 24180 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 14 ms 24008 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 14 ms 24088 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 46776 KB Output is correct
2 Correct 780 ms 59004 KB Output is correct
3 Execution timed out 4067 ms 67180 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 17 ms 24020 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 14 ms 23908 KB Output is correct
5 Correct 13 ms 23940 KB Output is correct
6 Correct 14 ms 24180 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 14 ms 24008 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 14 ms 24088 KB Output is correct
11 Incorrect 14 ms 24148 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 17 ms 24020 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 14 ms 23908 KB Output is correct
5 Correct 13 ms 23940 KB Output is correct
6 Correct 14 ms 24180 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 14 ms 24008 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 14 ms 24088 KB Output is correct
11 Incorrect 14 ms 24148 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 17 ms 24020 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 14 ms 23908 KB Output is correct
5 Correct 13 ms 23940 KB Output is correct
6 Correct 14 ms 24180 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 14 ms 24008 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 14 ms 24088 KB Output is correct
11 Correct 416 ms 46776 KB Output is correct
12 Correct 780 ms 59004 KB Output is correct
13 Execution timed out 4067 ms 67180 KB Time limit exceeded
14 Halted 0 ms 0 KB -