oj.uz

Submission #596094

# Submission time Handle Problem Language Result Execution time Memory
596094 2022-07-14T11:08:13 Z Bench0310 Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 70472 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});
        vector<int> path=find_path(a,b);
        if(cycle_edges.size()==1) new_valid(path);
        else if(cycle_edges.size()==2)
        {
            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 23764 KB Output is correct
2 Correct 15 ms 23996 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 13 ms 23860 KB Output is correct
5 Correct 14 ms 24036 KB Output is correct
6 Correct 15 ms 24144 KB Output is correct
7 Correct 16 ms 23892 KB Output is correct
8 Correct 15 ms 23988 KB Output is correct
9 Correct 14 ms 24144 KB Output is correct
10 Correct 14 ms 24020 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 46820 KB Output is correct
2 Correct 775 ms 59044 KB Output is correct
3 Execution timed out 4080 ms 70472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23996 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 13 ms 23860 KB Output is correct
5 Correct 14 ms 24036 KB Output is correct
6 Correct 15 ms 24144 KB Output is correct
7 Correct 16 ms 23892 KB Output is correct
8 Correct 15 ms 23988 KB Output is correct
9 Correct 14 ms 24144 KB Output is correct
10 Correct 14 ms 24020 KB Output is correct
11 Incorrect 16 ms 24060 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 15 ms 23996 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 13 ms 23860 KB Output is correct
5 Correct 14 ms 24036 KB Output is correct
6 Correct 15 ms 24144 KB Output is correct
7 Correct 16 ms 23892 KB Output is correct
8 Correct 15 ms 23988 KB Output is correct
9 Correct 14 ms 24144 KB Output is correct
10 Correct 14 ms 24020 KB Output is correct
11 Incorrect 16 ms 24060 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 15 ms 23996 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 13 ms 23860 KB Output is correct
5 Correct 14 ms 24036 KB Output is correct
6 Correct 15 ms 24144 KB Output is correct
7 Correct 16 ms 23892 KB Output is correct
8 Correct 15 ms 23988 KB Output is correct
9 Correct 14 ms 24144 KB Output is correct
10 Correct 14 ms 24020 KB Output is correct
11 Correct 415 ms 46820 KB Output is correct
12 Correct 775 ms 59044 KB Output is correct
13 Execution timed out 4080 ms 70472 KB Time limit exceeded
14 Halted 0 ms 0 KB -