oj.uz

Submission #596174

# Submission time Handle Problem Language Result Execution time Memory
596174 2022-07-14T12:55:19 Z Bench0310 Parachute rings (IOI12_rings) C++17
100 / 100
 1222 ms 122164 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
{
    vector<int> p;
    vector<int> sz;
    DSU()
    {
        p.assign(N,0);
        sz.assign(N,1);
        for(int i=0;i<N;i++) p[i]=i;
    }
    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;
    vector<int> id;
    int root;
    int tcnt=0;
    limiter(int r)
    {
        id.assign(N,-1);
        root=r;
        id[root]=-2;
        dfs(root,-1);
    }
    void dfs(int a,int p)
    {
        if(a!=root)
        {
            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 26 ms 55124 KB Output is correct
2 Correct 28 ms 55252 KB Output is correct
3 Correct 28 ms 55316 KB Output is correct
4 Correct 30 ms 55216 KB Output is correct
5 Correct 27 ms 55280 KB Output is correct
6 Correct 29 ms 55388 KB Output is correct
7 Correct 30 ms 55124 KB Output is correct
8 Correct 29 ms 55260 KB Output is correct
9 Correct 29 ms 55300 KB Output is correct
10 Correct 29 ms 55380 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 74292 KB Output is correct
2 Correct 853 ms 84452 KB Output is correct
3 Correct 1089 ms 99604 KB Output is correct
4 Correct 1039 ms 97000 KB Output is correct
5 Correct 1057 ms 99696 KB Output is correct
6 Correct 1153 ms 100276 KB Output is correct
7 Correct 1222 ms 122164 KB Output is correct
8 Correct 972 ms 89352 KB Output is correct
9 Correct 1020 ms 91524 KB Output is correct
10 Correct 755 ms 97632 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 55124 KB Output is correct
2 Correct 28 ms 55252 KB Output is correct
3 Correct 28 ms 55316 KB Output is correct
4 Correct 30 ms 55216 KB Output is correct
5 Correct 27 ms 55280 KB Output is correct
6 Correct 29 ms 55388 KB Output is correct
7 Correct 30 ms 55124 KB Output is correct
8 Correct 29 ms 55260 KB Output is correct
9 Correct 29 ms 55300 KB Output is correct
10 Correct 29 ms 55380 KB Output is correct
11 Correct 41 ms 78924 KB Output is correct
12 Correct 30 ms 55584 KB Output is correct
13 Correct 30 ms 55680 KB Output is correct
14 Correct 36 ms 67244 KB Output is correct
15 Correct 47 ms 67292 KB Output is correct
16 Correct 32 ms 55596 KB Output is correct
17 Correct 34 ms 55580 KB Output is correct
18 Correct 31 ms 55764 KB Output is correct
19 Correct 30 ms 55636 KB Output is correct
20 Correct 30 ms 55508 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 55124 KB Output is correct
2 Correct 28 ms 55252 KB Output is correct
3 Correct 28 ms 55316 KB Output is correct
4 Correct 30 ms 55216 KB Output is correct
5 Correct 27 ms 55280 KB Output is correct
6 Correct 29 ms 55388 KB Output is correct
7 Correct 30 ms 55124 KB Output is correct
8 Correct 29 ms 55260 KB Output is correct
9 Correct 29 ms 55300 KB Output is correct
10 Correct 29 ms 55380 KB Output is correct
11 Correct 41 ms 78924 KB Output is correct
12 Correct 30 ms 55584 KB Output is correct
13 Correct 30 ms 55680 KB Output is correct
14 Correct 36 ms 67244 KB Output is correct
15 Correct 47 ms 67292 KB Output is correct
16 Correct 32 ms 55596 KB Output is correct
17 Correct 34 ms 55580 KB Output is correct
18 Correct 31 ms 55764 KB Output is correct
19 Correct 30 ms 55636 KB Output is correct
20 Correct 30 ms 55508 KB Output is correct
21 Correct 43 ms 56396 KB Output is correct
22 Correct 52 ms 57128 KB Output is correct
23 Correct 62 ms 57660 KB Output is correct
24 Correct 84 ms 69864 KB Output is correct
25 Correct 44 ms 68708 KB Output is correct
26 Correct 63 ms 58588 KB Output is correct
27 Correct 65 ms 58400 KB Output is correct
28 Correct 66 ms 59124 KB Output is correct
29 Correct 64 ms 57836 KB Output is correct
30 Correct 93 ms 59812 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 55124 KB Output is correct
2 Correct 28 ms 55252 KB Output is correct
3 Correct 28 ms 55316 KB Output is correct
4 Correct 30 ms 55216 KB Output is correct
5 Correct 27 ms 55280 KB Output is correct
6 Correct 29 ms 55388 KB Output is correct
7 Correct 30 ms 55124 KB Output is correct
8 Correct 29 ms 55260 KB Output is correct
9 Correct 29 ms 55300 KB Output is correct
10 Correct 29 ms 55380 KB Output is correct
11 Correct 426 ms 74292 KB Output is correct
12 Correct 853 ms 84452 KB Output is correct
13 Correct 1089 ms 99604 KB Output is correct
14 Correct 1039 ms 97000 KB Output is correct
15 Correct 1057 ms 99696 KB Output is correct
16 Correct 1153 ms 100276 KB Output is correct
17 Correct 1222 ms 122164 KB Output is correct
18 Correct 972 ms 89352 KB Output is correct
19 Correct 1020 ms 91524 KB Output is correct
20 Correct 755 ms 97632 KB Output is correct
21 Correct 41 ms 78924 KB Output is correct
22 Correct 30 ms 55584 KB Output is correct
23 Correct 30 ms 55680 KB Output is correct
24 Correct 36 ms 67244 KB Output is correct
25 Correct 47 ms 67292 KB Output is correct
26 Correct 32 ms 55596 KB Output is correct
27 Correct 34 ms 55580 KB Output is correct
28 Correct 31 ms 55764 KB Output is correct
29 Correct 30 ms 55636 KB Output is correct
30 Correct 30 ms 55508 KB Output is correct
31 Correct 43 ms 56396 KB Output is correct
32 Correct 52 ms 57128 KB Output is correct
33 Correct 62 ms 57660 KB Output is correct
34 Correct 84 ms 69864 KB Output is correct
35 Correct 44 ms 68708 KB Output is correct
36 Correct 63 ms 58588 KB Output is correct
37 Correct 65 ms 58400 KB Output is correct
38 Correct 66 ms 59124 KB Output is correct
39 Correct 64 ms 57836 KB Output is correct
40 Correct 93 ms 59812 KB Output is correct
41 Correct 206 ms 66428 KB Output is correct
42 Correct 451 ms 75432 KB Output is correct
43 Correct 245 ms 81324 KB Output is correct
44 Correct 707 ms 93468 KB Output is correct
45 Correct 736 ms 91348 KB Output is correct
46 Correct 745 ms 89632 KB Output is correct
47 Correct 990 ms 94428 KB Output is correct
48 Correct 484 ms 80636 KB Output is correct
49 Correct 679 ms 85928 KB Output is correct
50 Correct 719 ms 85520 KB Output is correct
51 Correct 308 ms 81280 KB Output is correct
52 Correct 586 ms 86360 KB Output is correct
53 Correct 485 ms 81188 KB Output is correct
54 Correct 861 ms 85196 KB Output is correct
55 Correct 918 ms 87464 KB Output is correct