oj.uz

Submission #596155

# Submission time Handle Problem Language Result Execution time Memory
596155 2022-07-14T12:38:51 Z Bench0310 Parachute rings (IOI12_rings) C++17
38 / 100
 4000 ms 102276 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,vector<int> cc)
    {
        for(int x:cc) if(x==a) swap(a,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);
    }
};

vector<int> find_cc(int a)
{
    vector<int> q;
    auto add=[&](int x)
    {
        if(!vis[x])
        {
            q.push_back(x);
            vis[x]=1;
        }
    };
    add(a);
    int idx=0;
    while(idx<(int)q.size())
    {
        int e=q[idx++];
        for(int to:v[e]) add(to);
    }
    for(int x:q) vis[x]=0;
    return q;
}

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,find_cc(b));
            else if(l.inside(b)) l.add_subtree(a,b,find_cc(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 36 ms 66764 KB Output is correct
2 Correct 239 ms 67052 KB Output is correct
3 Correct 285 ms 67060 KB Output is correct
4 Correct 80 ms 67028 KB Output is correct
5 Correct 186 ms 66980 KB Output is correct
6 Correct 285 ms 67072 KB Output is correct
7 Correct 59 ms 66812 KB Output is correct
8 Correct 219 ms 67060 KB Output is correct
9 Correct 281 ms 67088 KB Output is correct
10 Correct 283 ms 67088 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 66764 KB Output is correct
2 Correct 239 ms 67052 KB Output is correct
3 Correct 285 ms 67060 KB Output is correct
4 Correct 80 ms 67028 KB Output is correct
5 Correct 186 ms 66980 KB Output is correct
6 Correct 285 ms 67072 KB Output is correct
7 Correct 59 ms 66812 KB Output is correct
8 Correct 219 ms 67060 KB Output is correct
9 Correct 281 ms 67088 KB Output is correct
10 Correct 283 ms 67088 KB Output is correct
11 Correct 299 ms 102276 KB Output is correct
12 Correct 542 ms 67396 KB Output is correct
13 Correct 552 ms 67356 KB Output is correct
14 Correct 389 ms 79044 KB Output is correct
15 Correct 358 ms 79132 KB Output is correct
16 Correct 551 ms 67404 KB Output is correct
17 Correct 461 ms 67420 KB Output is correct
18 Correct 558 ms 67664 KB Output is correct
19 Correct 562 ms 67560 KB Output is correct
20 Correct 560 ms 67340 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 66764 KB Output is correct
2 Correct 239 ms 67052 KB Output is correct
3 Correct 285 ms 67060 KB Output is correct
4 Correct 80 ms 67028 KB Output is correct
5 Correct 186 ms 66980 KB Output is correct
6 Correct 285 ms 67072 KB Output is correct
7 Correct 59 ms 66812 KB Output is correct
8 Correct 219 ms 67060 KB Output is correct
9 Correct 281 ms 67088 KB Output is correct
10 Correct 283 ms 67088 KB Output is correct
11 Correct 299 ms 102276 KB Output is correct
12 Correct 542 ms 67396 KB Output is correct
13 Correct 552 ms 67356 KB Output is correct
14 Correct 389 ms 79044 KB Output is correct
15 Correct 358 ms 79132 KB Output is correct
16 Correct 551 ms 67404 KB Output is correct
17 Correct 461 ms 67420 KB Output is correct
18 Correct 558 ms 67664 KB Output is correct
19 Correct 562 ms 67560 KB Output is correct
20 Correct 560 ms 67340 KB Output is correct
21 Correct 1422 ms 68376 KB Output is correct
22 Correct 2162 ms 69084 KB Output is correct
23 Correct 2728 ms 69824 KB Output is correct
24 Correct 2847 ms 82108 KB Output is correct
25 Correct 460 ms 80920 KB Output is correct
26 Correct 3386 ms 70588 KB Output is correct
27 Execution timed out 4038 ms 70340 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 66764 KB Output is correct
2 Correct 239 ms 67052 KB Output is correct
3 Correct 285 ms 67060 KB Output is correct
4 Correct 80 ms 67028 KB Output is correct
5 Correct 186 ms 66980 KB Output is correct
6 Correct 285 ms 67072 KB Output is correct
7 Correct 59 ms 66812 KB Output is correct
8 Correct 219 ms 67060 KB Output is correct
9 Correct 281 ms 67088 KB Output is correct
10 Correct 283 ms 67088 KB Output is correct
11 Execution timed out 4075 ms 72060 KB Time limit exceeded
12 Halted 0 ms 0 KB -