oj.uz

Submission #596101

# Submission time Handle Problem Language Result Execution time Memory
596101 2022-07-14T11:23:38 Z Bench0310 Parachute rings (IOI12_rings) C++17
37 / 100
 1085 ms 77880 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(cycle_edges.size()<=2)
        {
            for(auto [x,y]:cycle_edges)
            {
                if(x==a) updbig(y);
                if(y==a) updbig(x);
            }
        }
    }
    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 12 ms 23764 KB Output is correct
2 Correct 15 ms 24032 KB Output is correct
3 Correct 14 ms 24048 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 14 ms 24020 KB Output is correct
6 Correct 15 ms 24100 KB Output is correct
7 Correct 13 ms 23948 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24032 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 377 ms 46784 KB Output is correct
2 Correct 783 ms 59156 KB Output is correct
3 Correct 929 ms 69356 KB Output is correct
4 Correct 978 ms 73272 KB Output is correct
5 Correct 1077 ms 75964 KB Output is correct
6 Correct 1085 ms 76556 KB Output is correct
7 Correct 970 ms 69568 KB Output is correct
8 Correct 946 ms 65152 KB Output is correct
9 Correct 993 ms 67868 KB Output is correct
10 Correct 717 ms 77880 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 15 ms 24032 KB Output is correct
3 Correct 14 ms 24048 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 14 ms 24020 KB Output is correct
6 Correct 15 ms 24100 KB Output is correct
7 Correct 13 ms 23948 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24032 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Correct 17 ms 24148 KB Output is correct
12 Correct 16 ms 24416 KB Output is correct
13 Correct 16 ms 24372 KB Output is correct
14 Incorrect 16 ms 24148 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 15 ms 24032 KB Output is correct
3 Correct 14 ms 24048 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 14 ms 24020 KB Output is correct
6 Correct 15 ms 24100 KB Output is correct
7 Correct 13 ms 23948 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24032 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Correct 17 ms 24148 KB Output is correct
12 Correct 16 ms 24416 KB Output is correct
13 Correct 16 ms 24372 KB Output is correct
14 Incorrect 16 ms 24148 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 15 ms 24032 KB Output is correct
3 Correct 14 ms 24048 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 14 ms 24020 KB Output is correct
6 Correct 15 ms 24100 KB Output is correct
7 Correct 13 ms 23948 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24032 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Correct 377 ms 46784 KB Output is correct
12 Correct 783 ms 59156 KB Output is correct
13 Correct 929 ms 69356 KB Output is correct
14 Correct 978 ms 73272 KB Output is correct
15 Correct 1077 ms 75964 KB Output is correct
16 Correct 1085 ms 76556 KB Output is correct
17 Correct 970 ms 69568 KB Output is correct
18 Correct 946 ms 65152 KB Output is correct
19 Correct 993 ms 67868 KB Output is correct
20 Correct 717 ms 77880 KB Output is correct
21 Correct 17 ms 24148 KB Output is correct
22 Correct 16 ms 24416 KB Output is correct
23 Correct 16 ms 24372 KB Output is correct
24 Incorrect 16 ms 24148 KB Output isn't correct
25 Halted 0 ms 0 KB -