oj.uz

Submission #596097

# Submission time Handle Problem Language Result Execution time Memory
596097 2022-07-14T11:13:04 Z Bench0310 Parachute rings (IOI12_rings) C++17
37 / 100
 1076 ms 77712 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]+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 13 ms 24020 KB Output is correct
3 Correct 14 ms 24052 KB Output is correct
4 Correct 12 ms 23808 KB Output is correct
5 Correct 13 ms 24036 KB Output is correct
6 Correct 14 ms 24132 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 46680 KB Output is correct
2 Correct 802 ms 58964 KB Output is correct
3 Correct 993 ms 69316 KB Output is correct
4 Correct 1004 ms 73268 KB Output is correct
5 Correct 1034 ms 75840 KB Output is correct
6 Correct 1076 ms 76448 KB Output is correct
7 Correct 935 ms 69596 KB Output is correct
8 Correct 949 ms 65076 KB Output is correct
9 Correct 1030 ms 67676 KB Output is correct
10 Correct 722 ms 77712 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 13 ms 24020 KB Output is correct
3 Correct 14 ms 24052 KB Output is correct
4 Correct 12 ms 23808 KB Output is correct
5 Correct 13 ms 24036 KB Output is correct
6 Correct 14 ms 24132 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Incorrect 14 ms 24120 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 13 ms 24020 KB Output is correct
3 Correct 14 ms 24052 KB Output is correct
4 Correct 12 ms 23808 KB Output is correct
5 Correct 13 ms 24036 KB Output is correct
6 Correct 14 ms 24132 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Incorrect 14 ms 24120 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 13 ms 24020 KB Output is correct
3 Correct 14 ms 24052 KB Output is correct
4 Correct 12 ms 23808 KB Output is correct
5 Correct 13 ms 24036 KB Output is correct
6 Correct 14 ms 24132 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Correct 407 ms 46680 KB Output is correct
12 Correct 802 ms 58964 KB Output is correct
13 Correct 993 ms 69316 KB Output is correct
14 Correct 1004 ms 73268 KB Output is correct
15 Correct 1034 ms 75840 KB Output is correct
16 Correct 1076 ms 76448 KB Output is correct
17 Correct 935 ms 69596 KB Output is correct
18 Correct 949 ms 65076 KB Output is correct
19 Correct 1030 ms 67676 KB Output is correct
20 Correct 722 ms 77712 KB Output is correct
21 Incorrect 14 ms 24120 KB Output isn't correct
22 Halted 0 ms 0 KB -