oj.uz

Submission #596157

# Submission time Handle Problem Language Result Execution time Memory
596157 2022-07-14T12:41:46 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)
        {
            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 33 ms 66764 KB Output is correct
2 Correct 245 ms 67048 KB Output is correct
3 Correct 284 ms 67064 KB Output is correct
4 Correct 82 ms 66888 KB Output is correct
5 Correct 171 ms 67084 KB Output is correct
6 Correct 276 ms 67108 KB Output is correct
7 Correct 60 ms 66928 KB Output is correct
8 Correct 230 ms 67060 KB Output is correct
9 Correct 288 ms 67088 KB Output is correct
10 Correct 273 ms 67064 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 66764 KB Output is correct
2 Correct 245 ms 67048 KB Output is correct
3 Correct 284 ms 67064 KB Output is correct
4 Correct 82 ms 66888 KB Output is correct
5 Correct 171 ms 67084 KB Output is correct
6 Correct 276 ms 67108 KB Output is correct
7 Correct 60 ms 66928 KB Output is correct
8 Correct 230 ms 67060 KB Output is correct
9 Correct 288 ms 67088 KB Output is correct
10 Correct 273 ms 67064 KB Output is correct
11 Correct 314 ms 102368 KB Output is correct
12 Correct 574 ms 67436 KB Output is correct
13 Correct 544 ms 67440 KB Output is correct
14 Correct 399 ms 78968 KB Output is correct
15 Correct 365 ms 79080 KB Output is correct
16 Correct 545 ms 67240 KB Output is correct
17 Correct 512 ms 67292 KB Output is correct
18 Correct 553 ms 67916 KB Output is correct
19 Correct 493 ms 67348 KB Output is correct
20 Correct 524 ms 67292 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 66764 KB Output is correct
2 Correct 245 ms 67048 KB Output is correct
3 Correct 284 ms 67064 KB Output is correct
4 Correct 82 ms 66888 KB Output is correct
5 Correct 171 ms 67084 KB Output is correct
6 Correct 276 ms 67108 KB Output is correct
7 Correct 60 ms 66928 KB Output is correct
8 Correct 230 ms 67060 KB Output is correct
9 Correct 288 ms 67088 KB Output is correct
10 Correct 273 ms 67064 KB Output is correct
11 Correct 314 ms 102368 KB Output is correct
12 Correct 574 ms 67436 KB Output is correct
13 Correct 544 ms 67440 KB Output is correct
14 Correct 399 ms 78968 KB Output is correct
15 Correct 365 ms 79080 KB Output is correct
16 Correct 545 ms 67240 KB Output is correct
17 Correct 512 ms 67292 KB Output is correct
18 Correct 553 ms 67916 KB Output is correct
19 Correct 493 ms 67348 KB Output is correct
20 Correct 524 ms 67292 KB Output is correct
21 Correct 1432 ms 68088 KB Output is correct
22 Correct 2145 ms 68952 KB Output is correct
23 Correct 2806 ms 69476 KB Output is correct
24 Correct 2773 ms 81676 KB Output is correct
25 Correct 449 ms 80468 KB Output is correct
26 Correct 3231 ms 70504 KB Output is correct
27 Execution timed out 4050 ms 70056 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 66764 KB Output is correct
2 Correct 245 ms 67048 KB Output is correct
3 Correct 284 ms 67064 KB Output is correct
4 Correct 82 ms 66888 KB Output is correct
5 Correct 171 ms 67084 KB Output is correct
6 Correct 276 ms 67108 KB Output is correct
7 Correct 60 ms 66928 KB Output is correct
8 Correct 230 ms 67060 KB Output is correct
9 Correct 288 ms 67088 KB Output is correct
10 Correct 273 ms 67064 KB Output is correct
11 Execution timed out 4043 ms 72156 KB Time limit exceeded
12 Halted 0 ms 0 KB -