oj.uz

Submission #596099

# Submission time Handle Problem Language Result Execution time Memory
596099 2022-07-14T11:19:14 Z Bench0310 Parachute rings (IOI12_rings) C++17
37 / 100
 1109 ms 77828 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 if(cycle_edges.size()==3) new_valid({});
    }
    upddeg(a);
    upddeg(b);
}

int CountCritical()
{
    if(four.size()==0) return cnt[bad]+(bad>0?cntbad[bad-1]:0);
    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 13 ms 23764 KB Output is correct
2 Correct 18 ms 24020 KB Output is correct
3 Correct 15 ms 24072 KB Output is correct
4 Correct 13 ms 23852 KB Output is correct
5 Correct 16 ms 24020 KB Output is correct
6 Correct 14 ms 24096 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 14 ms 24100 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 14 ms 24020 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 46776 KB Output is correct
2 Correct 801 ms 59004 KB Output is correct
3 Correct 980 ms 69268 KB Output is correct
4 Correct 1002 ms 73348 KB Output is correct
5 Correct 1039 ms 75748 KB Output is correct
6 Correct 1109 ms 76632 KB Output is correct
7 Correct 924 ms 69548 KB Output is correct
8 Correct 925 ms 64936 KB Output is correct
9 Correct 987 ms 67932 KB Output is correct
10 Correct 744 ms 77828 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 18 ms 24020 KB Output is correct
3 Correct 15 ms 24072 KB Output is correct
4 Correct 13 ms 23852 KB Output is correct
5 Correct 16 ms 24020 KB Output is correct
6 Correct 14 ms 24096 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 14 ms 24100 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 14 ms 24020 KB Output is correct
11 Incorrect 16 ms 24276 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 18 ms 24020 KB Output is correct
3 Correct 15 ms 24072 KB Output is correct
4 Correct 13 ms 23852 KB Output is correct
5 Correct 16 ms 24020 KB Output is correct
6 Correct 14 ms 24096 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 14 ms 24100 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 14 ms 24020 KB Output is correct
11 Incorrect 16 ms 24276 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 18 ms 24020 KB Output is correct
3 Correct 15 ms 24072 KB Output is correct
4 Correct 13 ms 23852 KB Output is correct
5 Correct 16 ms 24020 KB Output is correct
6 Correct 14 ms 24096 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 14 ms 24100 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 14 ms 24020 KB Output is correct
11 Correct 406 ms 46776 KB Output is correct
12 Correct 801 ms 59004 KB Output is correct
13 Correct 980 ms 69268 KB Output is correct
14 Correct 1002 ms 73348 KB Output is correct
15 Correct 1039 ms 75748 KB Output is correct
16 Correct 1109 ms 76632 KB Output is correct
17 Correct 924 ms 69548 KB Output is correct
18 Correct 925 ms 64936 KB Output is correct
19 Correct 987 ms 67932 KB Output is correct
20 Correct 744 ms 77828 KB Output is correct
21 Incorrect 16 ms 24276 KB Output isn't correct
22 Halted 0 ms 0 KB -