oj.uz

Submission #1013439

# Submission time Handle Problem Language Result Execution time Memory
1013439 2024-07-03T14:33:21 Z Ludissey Parachute rings (IOI12_rings) C++14
20 / 100
 3395 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
int n;
bool hasloop=false;
vector<vector<int>> neigh;
vector<int> visited;
vector<int> parent;
vector<int> pr;
vector<int> sz;
vector<int> crit;
vector<int> incycle;
vector<int> iscycle;
vector<int> orig;
int timer=0;
int exceptation=-1;
bool cycl=0;
int cc=0;
int c=0;
int upds=0;

int getParent(int a) { return parent[a]==a ? a : parent[a]=getParent(parent[a]); }

void unite(int a, int b){
    a=getParent(a); b=getParent(b);
    if(a==b) return;
    if(sz[b]>sz[a]) swap(a,b);
    sz[a]+=sz[b];
    parent[a]=b;
}

void detect_cycle(int x, int p) {
    if(visited[x]==2) return;
    if (visited[x] == 1) {
        vector<int> v;
        iscycle[x]=true;
        incycle.push_back(x);
        int cr=pr[x];
        while (cr!=x) {
            incycle.push_back(cr);
            iscycle[cr]=true;
            cr=pr[cr];
        } 
        return;
    }
    pr[x]=p;
    visited[x]=1;
    for (int to : neigh[x]) {
        if (to==p) continue;
        detect_cycle(to,x);
    }
    visited[x]=2;
}


void get_origin(int x, int p,int og) {
    orig[x]=og;
    for (int to : neigh[x]) {
        if (to==p||iscycle[to]) continue;
        get_origin(to,x,orig[x]);
    }
}

void Init(signed N_) {
    n = N_;
    parent.resize(n);
    visited.resize(n,0);
    neigh.resize(n);
    orig.resize(n,-1);
    cc=0;
    sz.resize(n,1);
    iscycle.resize(n,0);
    pr.resize(n,-1);
    crit.resize(n,0);
    upds=0;
    for (int i = 0; i < n; i++) parent[i]=i;
}

void update_crit(int X){
    if(sz(neigh[X])==3){
        crit[neigh[X][0]]++;
        crit[neigh[X][1]]++;
        crit[neigh[X][2]]++;
        crit[X]++;
        upds++;
    }else if(sz(neigh[X])>3){
        crit[X]++;
        upds++;
    }
}

void case1(int A, int B){ //two vertex of different sets O(1);
    unite(A,B);
    if(orig[A]>=0&&orig[B]<0) get_origin(B,A,orig[A]);
    else if(orig[B]>=0&&orig[A]<0) get_origin(A,B,orig[B]);
    update_crit(A);
    update_crit(B);
}
void case2(int A, int B){ //two vertex of same sets !! NO CYCLE !! O(N+M)
    detect_cycle(A,B);
    cycl=1;
    for (int i = 0; i < sz(incycle); i++) crit[incycle[i]]++;
    upds++;
    visited.clear();
    visited.resize(n,0);
    for (int i = 0; i < sz(incycle); i++) get_origin(incycle[i],-1,incycle[i]);
    case1(A,B);
}
void case3(int A, int B){ //two vertex of same sets !! CYCLE !! O(1)
    //cerr << "case 3";
    if(orig[A]<0||orig[B]<0) { upds++; return; }
    crit[orig[A]]++;
    if(orig[A]!=orig[B]) crit[orig[B]]++;
    upds++;
    update_crit(A);
    update_crit(B);
    update_crit(orig[A]);
    update_crit(orig[B]);
}
void Link(signed A, signed B) {
    neigh[A].push_back(B);
    neigh[B].push_back(A);
    if(getParent(A)==getParent(B)){
        if(cycl) case3(A,B);
        else case2(A,B);
    }else{
        case1(A,B);
    }
}

signed CountCritical() {
    c=0;
    for (int i = 0; i < n; i++) if(crit[i]==upds) c++;
    return c;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 2 ms 1192 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 1072 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 64376 KB Output is correct
2 Correct 538 ms 98728 KB Output is correct
3 Runtime error 3395 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 2 ms 1192 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 1072 KB Output is correct
11 Correct 2 ms 1116 KB Output is correct
12 Runtime error 328 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 2 ms 1192 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 1072 KB Output is correct
11 Correct 2 ms 1116 KB Output is correct
12 Runtime error 328 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 2 ms 1192 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 1072 KB Output is correct
11 Correct 225 ms 64376 KB Output is correct
12 Correct 538 ms 98728 KB Output is correct
13 Runtime error 3395 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -