oj.uz

Submission #596158

# Submission time Handle Problem Language Result Execution time Memory
596158 2022-07-14T12:42:27 Z Bench0310 Parachute rings (IOI12_rings) C++17
38 / 100
 4000 ms 102360 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));
            assert(opt.size()<=2);
            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 34 ms 66772 KB Output is correct
2 Correct 259 ms 67264 KB Output is correct
3 Correct 290 ms 67084 KB Output is correct
4 Correct 76 ms 66908 KB Output is correct
5 Correct 158 ms 66956 KB Output is correct
6 Correct 294 ms 67248 KB Output is correct
7 Correct 60 ms 66920 KB Output is correct
8 Correct 223 ms 67064 KB Output is correct
9 Correct 221 ms 67184 KB Output is correct
10 Correct 272 ms 67156 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 66772 KB Output is correct
2 Correct 259 ms 67264 KB Output is correct
3 Correct 290 ms 67084 KB Output is correct
4 Correct 76 ms 66908 KB Output is correct
5 Correct 158 ms 66956 KB Output is correct
6 Correct 294 ms 67248 KB Output is correct
7 Correct 60 ms 66920 KB Output is correct
8 Correct 223 ms 67064 KB Output is correct
9 Correct 221 ms 67184 KB Output is correct
10 Correct 272 ms 67156 KB Output is correct
11 Correct 268 ms 102360 KB Output is correct
12 Correct 555 ms 67340 KB Output is correct
13 Correct 555 ms 67492 KB Output is correct
14 Correct 378 ms 79072 KB Output is correct
15 Correct 356 ms 79116 KB Output is correct
16 Correct 553 ms 67336 KB Output is correct
17 Correct 528 ms 67412 KB Output is correct
18 Correct 558 ms 67668 KB Output is correct
19 Correct 558 ms 67244 KB Output is correct
20 Correct 526 ms 67332 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 66772 KB Output is correct
2 Correct 259 ms 67264 KB Output is correct
3 Correct 290 ms 67084 KB Output is correct
4 Correct 76 ms 66908 KB Output is correct
5 Correct 158 ms 66956 KB Output is correct
6 Correct 294 ms 67248 KB Output is correct
7 Correct 60 ms 66920 KB Output is correct
8 Correct 223 ms 67064 KB Output is correct
9 Correct 221 ms 67184 KB Output is correct
10 Correct 272 ms 67156 KB Output is correct
11 Correct 268 ms 102360 KB Output is correct
12 Correct 555 ms 67340 KB Output is correct
13 Correct 555 ms 67492 KB Output is correct
14 Correct 378 ms 79072 KB Output is correct
15 Correct 356 ms 79116 KB Output is correct
16 Correct 553 ms 67336 KB Output is correct
17 Correct 528 ms 67412 KB Output is correct
18 Correct 558 ms 67668 KB Output is correct
19 Correct 558 ms 67244 KB Output is correct
20 Correct 526 ms 67332 KB Output is correct
21 Correct 1347 ms 68348 KB Output is correct
22 Correct 2215 ms 69060 KB Output is correct
23 Correct 2747 ms 69432 KB Output is correct
24 Correct 2897 ms 81660 KB Output is correct
25 Correct 437 ms 80632 KB Output is correct
26 Correct 3535 ms 70272 KB Output is correct
27 Execution timed out 4062 ms 70036 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 66772 KB Output is correct
2 Correct 259 ms 67264 KB Output is correct
3 Correct 290 ms 67084 KB Output is correct
4 Correct 76 ms 66908 KB Output is correct
5 Correct 158 ms 66956 KB Output is correct
6 Correct 294 ms 67248 KB Output is correct
7 Correct 60 ms 66920 KB Output is correct
8 Correct 223 ms 67064 KB Output is correct
9 Correct 221 ms 67184 KB Output is correct
10 Correct 272 ms 67156 KB Output is correct
11 Execution timed out 4049 ms 72036 KB Time limit exceeded
12 Halted 0 ms 0 KB -