oj.uz

Submission #596163

# Submission time Handle Problem Language Result Execution time Memory
596163 2022-07-14T12:45:25 Z Bench0310 Parachute rings (IOI12_rings) C++17
38 / 100
 4000 ms 102368 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=1000000;
int n;
vector<int> v[N];
vector<int> vc[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;
vector<array<int,2>> cycle_edges;
int incycle[N];
bool valid[N];
struct limiter;
vector<limiter> lim;
bool vis[N];

struct DSU
{
    int p[N];
    int sz[N];
    DSU()
    {
        for(int i=0;i<N;i++)
        {
            p[i]=i;
            sz[i]=1;
        }
    }
    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;
    }
}dsu;

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++) 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);
        for(int to:vc[a]) updbig(to);
    }
    if(deg[a]==4) four.push_back(a);
}

void rm_valid(int a)
{
    if(valid[a])
    {
        upd(a,-1);
        valid[a]=0;
    }
}

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]) rm_valid(i);
    }
}

struct limiter
{
    DSU d;
    int id[N];
    int root;
    int tcnt=0;
    limiter(int r)
    {
        memset(id,-1,sizeof(id));
        root=r;
        id[root]=-2;
        dfs(root,-1);
    }
    void dfs(int a,int p)
    {
        if(a!=root)
        {
            assert(id[a]==-1);
            if(p==root) id[a]=(tcnt++);
            else id[a]=id[p];
        }
        for(int to:v[a]) if(to!=p) dfs(to,a);
    }
    bool inside(int a){return (id[a]!=-1);}
    void add_subtree(int a,int b)
    {
        dfs(b,a);
    }
    void add_cycle(int a,int b)
    {
        if(a!=root&&b!=root&&d.merge_sets(id[a],id[b])==0) rm_valid(root);
    }
};

void Link(int a, int b)
{
    if(dsu.merge_sets(a,b)==1)
    {
        for(limiter &l:lim)
        {
            if(l.inside(a)) l.add_subtree(a,b);
            else if(l.inside(b)) l.add_subtree(b,a);
        }
        v[a].push_back(b);
        v[b].push_back(a);
    }
    else
    {
        vc[a].push_back(b);
        vc[b].push_back(a);
        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);
            for(int x:opt) lim.push_back(limiter(x));
            for(limiter &l:lim)
            {
                for(auto [x,y]:cycle_edges)
                {
                    if(l.inside(x)) l.add_cycle(x,y);
                    else rm_valid(l.root);
                }
            }
        }
        else if(cycle_edges.size()>=3)
        {
            for(limiter &l:lim)
            {
                if(l.inside(a)) l.add_cycle(a,b);
                else rm_valid(l.root);
            }
        }
    }
    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 35 ms 66808 KB Output is correct
2 Correct 247 ms 67056 KB Output is correct
3 Correct 280 ms 67148 KB Output is correct
4 Correct 81 ms 66944 KB Output is correct
5 Correct 176 ms 66912 KB Output is correct
6 Correct 282 ms 67068 KB Output is correct
7 Correct 61 ms 66868 KB Output is correct
8 Correct 233 ms 67052 KB Output is correct
9 Correct 288 ms 67208 KB Output is correct
10 Correct 281 ms 67080 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4085 ms 71896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 66808 KB Output is correct
2 Correct 247 ms 67056 KB Output is correct
3 Correct 280 ms 67148 KB Output is correct
4 Correct 81 ms 66944 KB Output is correct
5 Correct 176 ms 66912 KB Output is correct
6 Correct 282 ms 67068 KB Output is correct
7 Correct 61 ms 66868 KB Output is correct
8 Correct 233 ms 67052 KB Output is correct
9 Correct 288 ms 67208 KB Output is correct
10 Correct 281 ms 67080 KB Output is correct
11 Correct 310 ms 102368 KB Output is correct
12 Correct 551 ms 67328 KB Output is correct
13 Correct 578 ms 67436 KB Output is correct
14 Correct 384 ms 79040 KB Output is correct
15 Correct 354 ms 79164 KB Output is correct
16 Correct 545 ms 67396 KB Output is correct
17 Correct 540 ms 67324 KB Output is correct
18 Correct 553 ms 67624 KB Output is correct
19 Correct 548 ms 67244 KB Output is correct
20 Correct 544 ms 67248 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 66808 KB Output is correct
2 Correct 247 ms 67056 KB Output is correct
3 Correct 280 ms 67148 KB Output is correct
4 Correct 81 ms 66944 KB Output is correct
5 Correct 176 ms 66912 KB Output is correct
6 Correct 282 ms 67068 KB Output is correct
7 Correct 61 ms 66868 KB Output is correct
8 Correct 233 ms 67052 KB Output is correct
9 Correct 288 ms 67208 KB Output is correct
10 Correct 281 ms 67080 KB Output is correct
11 Correct 310 ms 102368 KB Output is correct
12 Correct 551 ms 67328 KB Output is correct
13 Correct 578 ms 67436 KB Output is correct
14 Correct 384 ms 79040 KB Output is correct
15 Correct 354 ms 79164 KB Output is correct
16 Correct 545 ms 67396 KB Output is correct
17 Correct 540 ms 67324 KB Output is correct
18 Correct 553 ms 67624 KB Output is correct
19 Correct 548 ms 67244 KB Output is correct
20 Correct 544 ms 67248 KB Output is correct
21 Correct 1442 ms 68184 KB Output is correct
22 Correct 2096 ms 68832 KB Output is correct
23 Correct 2558 ms 69432 KB Output is correct
24 Correct 2801 ms 81644 KB Output is correct
25 Correct 447 ms 80504 KB Output is correct
26 Correct 3561 ms 70256 KB Output is correct
27 Execution timed out 4083 ms 70140 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 66808 KB Output is correct
2 Correct 247 ms 67056 KB Output is correct
3 Correct 280 ms 67148 KB Output is correct
4 Correct 81 ms 66944 KB Output is correct
5 Correct 176 ms 66912 KB Output is correct
6 Correct 282 ms 67068 KB Output is correct
7 Correct 61 ms 66868 KB Output is correct
8 Correct 233 ms 67052 KB Output is correct
9 Correct 288 ms 67208 KB Output is correct
10 Correct 281 ms 67080 KB Output is correct
11 Execution timed out 4085 ms 71896 KB Time limit exceeded
12 Halted 0 ms 0 KB -