oj.uz

Submission #596148

# Submission time Handle Problem Language Result Execution time Memory
596148 2022-07-14T12:24:11 Z Bench0310 Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 78872 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) l.add_cycle(x,y);
        }
        else if(cycle_edges.size()==3)
        {
            for(limiter &l:lim) l.add_cycle(a,b);
        }
    }
    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 24 ms 43348 KB Output is correct
2 Correct 233 ms 43576 KB Output is correct
3 Correct 272 ms 43764 KB Output is correct
4 Correct 69 ms 43596 KB Output is correct
5 Correct 174 ms 43424 KB Output is correct
6 Correct 269 ms 43644 KB Output is correct
7 Correct 49 ms 43348 KB Output is correct
8 Correct 205 ms 43528 KB Output is correct
9 Correct 273 ms 43592 KB Output is correct
10 Correct 274 ms 43560 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43348 KB Output is correct
2 Correct 233 ms 43576 KB Output is correct
3 Correct 272 ms 43764 KB Output is correct
4 Correct 69 ms 43596 KB Output is correct
5 Correct 174 ms 43424 KB Output is correct
6 Correct 269 ms 43644 KB Output is correct
7 Correct 49 ms 43348 KB Output is correct
8 Correct 205 ms 43528 KB Output is correct
9 Correct 273 ms 43592 KB Output is correct
10 Correct 274 ms 43560 KB Output is correct
11 Correct 285 ms 78872 KB Output is correct
12 Correct 520 ms 43936 KB Output is correct
13 Correct 479 ms 43960 KB Output is correct
14 Incorrect 370 ms 55576 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43348 KB Output is correct
2 Correct 233 ms 43576 KB Output is correct
3 Correct 272 ms 43764 KB Output is correct
4 Correct 69 ms 43596 KB Output is correct
5 Correct 174 ms 43424 KB Output is correct
6 Correct 269 ms 43644 KB Output is correct
7 Correct 49 ms 43348 KB Output is correct
8 Correct 205 ms 43528 KB Output is correct
9 Correct 273 ms 43592 KB Output is correct
10 Correct 274 ms 43560 KB Output is correct
11 Correct 285 ms 78872 KB Output is correct
12 Correct 520 ms 43936 KB Output is correct
13 Correct 479 ms 43960 KB Output is correct
14 Incorrect 370 ms 55576 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43348 KB Output is correct
2 Correct 233 ms 43576 KB Output is correct
3 Correct 272 ms 43764 KB Output is correct
4 Correct 69 ms 43596 KB Output is correct
5 Correct 174 ms 43424 KB Output is correct
6 Correct 269 ms 43644 KB Output is correct
7 Correct 49 ms 43348 KB Output is correct
8 Correct 205 ms 43528 KB Output is correct
9 Correct 273 ms 43592 KB Output is correct
10 Correct 274 ms 43560 KB Output is correct
11 Execution timed out 4067 ms 48780 KB Time limit exceeded
12 Halted 0 ms 0 KB -