oj.uz

Submission #596152

# Submission time Handle Problem Language Result Execution time Memory
596152 2022-07-14T12:29:59 Z Bench0310 Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 78840 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=1000000;
int n;
vector<int> v[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);
        if(cycle_edges.size()<=2)
        {
            for(auto [x,y]:cycle_edges)
            {
                if(x==a) updbig(y);
                if(y==a) updbig(x);
            }
        }
    }
    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
    {
        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 25 ms 43348 KB Output is correct
2 Correct 237 ms 43600 KB Output is correct
3 Correct 271 ms 43596 KB Output is correct
4 Correct 67 ms 43536 KB Output is correct
5 Correct 174 ms 43596 KB Output is correct
6 Correct 275 ms 43704 KB Output is correct
7 Correct 52 ms 43416 KB Output is correct
8 Correct 216 ms 43720 KB Output is correct
9 Correct 271 ms 43656 KB Output is correct
10 Correct 275 ms 43580 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 43348 KB Output is correct
2 Correct 237 ms 43600 KB Output is correct
3 Correct 271 ms 43596 KB Output is correct
4 Correct 67 ms 43536 KB Output is correct
5 Correct 174 ms 43596 KB Output is correct
6 Correct 275 ms 43704 KB Output is correct
7 Correct 52 ms 43416 KB Output is correct
8 Correct 216 ms 43720 KB Output is correct
9 Correct 271 ms 43656 KB Output is correct
10 Correct 275 ms 43580 KB Output is correct
11 Correct 296 ms 78840 KB Output is correct
12 Correct 527 ms 44012 KB Output is correct
13 Correct 538 ms 43904 KB Output is correct
14 Incorrect 372 ms 55520 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 43348 KB Output is correct
2 Correct 237 ms 43600 KB Output is correct
3 Correct 271 ms 43596 KB Output is correct
4 Correct 67 ms 43536 KB Output is correct
5 Correct 174 ms 43596 KB Output is correct
6 Correct 275 ms 43704 KB Output is correct
7 Correct 52 ms 43416 KB Output is correct
8 Correct 216 ms 43720 KB Output is correct
9 Correct 271 ms 43656 KB Output is correct
10 Correct 275 ms 43580 KB Output is correct
11 Correct 296 ms 78840 KB Output is correct
12 Correct 527 ms 44012 KB Output is correct
13 Correct 538 ms 43904 KB Output is correct
14 Incorrect 372 ms 55520 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 43348 KB Output is correct
2 Correct 237 ms 43600 KB Output is correct
3 Correct 271 ms 43596 KB Output is correct
4 Correct 67 ms 43536 KB Output is correct
5 Correct 174 ms 43596 KB Output is correct
6 Correct 275 ms 43704 KB Output is correct
7 Correct 52 ms 43416 KB Output is correct
8 Correct 216 ms 43720 KB Output is correct
9 Correct 271 ms 43656 KB Output is correct
10 Correct 275 ms 43580 KB Output is correct
11 Execution timed out 4077 ms 48504 KB Time limit exceeded
12 Halted 0 ms 0 KB -