oj.uz

Submission #596095

# Submission time Handle Problem Language Result Execution time Memory
596095 2022-07-14T11:10:12 Z Bench0310 Parachute rings (IOI12_rings) C++17
37 / 100
 1120 ms 76684 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);
        }
    }
    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 13 ms 23724 KB Output is correct
2 Correct 15 ms 24020 KB Output is correct
3 Correct 15 ms 24072 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 14 ms 23956 KB Output is correct
6 Correct 17 ms 24092 KB Output is correct
7 Correct 12 ms 23860 KB Output is correct
8 Correct 14 ms 24104 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 16 ms 24020 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 46764 KB Output is correct
2 Correct 786 ms 59000 KB Output is correct
3 Correct 991 ms 69252 KB Output is correct
4 Correct 1016 ms 73332 KB Output is correct
5 Correct 1002 ms 75796 KB Output is correct
6 Correct 1120 ms 76684 KB Output is correct
7 Correct 932 ms 69424 KB Output is correct
8 Correct 945 ms 65032 KB Output is correct
9 Correct 997 ms 67728 KB Output is correct
10 Correct 734 ms 73908 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23724 KB Output is correct
2 Correct 15 ms 24020 KB Output is correct
3 Correct 15 ms 24072 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 14 ms 23956 KB Output is correct
6 Correct 17 ms 24092 KB Output is correct
7 Correct 12 ms 23860 KB Output is correct
8 Correct 14 ms 24104 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 16 ms 24020 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 13 ms 23724 KB Output is correct
2 Correct 15 ms 24020 KB Output is correct
3 Correct 15 ms 24072 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 14 ms 23956 KB Output is correct
6 Correct 17 ms 24092 KB Output is correct
7 Correct 12 ms 23860 KB Output is correct
8 Correct 14 ms 24104 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 16 ms 24020 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 13 ms 23724 KB Output is correct
2 Correct 15 ms 24020 KB Output is correct
3 Correct 15 ms 24072 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 14 ms 23956 KB Output is correct
6 Correct 17 ms 24092 KB Output is correct
7 Correct 12 ms 23860 KB Output is correct
8 Correct 14 ms 24104 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 16 ms 24020 KB Output is correct
11 Correct 384 ms 46764 KB Output is correct
12 Correct 786 ms 59000 KB Output is correct
13 Correct 991 ms 69252 KB Output is correct
14 Correct 1016 ms 73332 KB Output is correct
15 Correct 1002 ms 75796 KB Output is correct
16 Correct 1120 ms 76684 KB Output is correct
17 Correct 932 ms 69424 KB Output is correct
18 Correct 945 ms 65032 KB Output is correct
19 Correct 997 ms 67728 KB Output is correct
20 Correct 734 ms 73908 KB Output is correct
21 Incorrect 14 ms 24148 KB Output isn't correct
22 Halted 0 ms 0 KB -