oj.uz

Submission #760688

# Submission time Handle Problem Language Result Execution time Memory
760688 2023-06-18T07:21:42 Z fatemetmhr Parachute rings (IOI12_rings) C++17
37 / 100
 1102 ms 84556 KB 
//  ~ Be Name Khoda ~  //

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e6   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int n;
bool found = false;
bool cy = false, morecy = false, mark[maxn5];
int cynum = 0;
vector <int> adj[maxn5];


struct _dsu{

    int remver, par[maxn5];
    bool noans;

    _dsu(){
        remver = -1;
        noans = false;
        memset(par, -1, sizeof par);
    }

    int get_par(int a){return par[a] < 0 ? a : par[a] = get_par(par[a]);}

    inline void add(int a, int b){
        if(a == remver || b == remver || a == b)
            return;
        a = get_par(a);
        b = get_par(b);
        if(a == b){
            noans = true;
            if(cy)
                morecy = true;
            else{
                cy = true;
                cynum = -par[a];
            }
            return;
        }
        if(-par[a] < -par[b])
            swap(a, b);
        par[a] += par[b];
        par[b] = a;
    }

} dsu[6];


void Init(int N_) {
    n = N_;
}

void Link(int a, int b){
    adj[a].pb(b);
    adj[b].pb(a);
    dsu[0].add(a, b);
    if(found) for(int i = 1; i < 5; i++)
        dsu[i].add(a, b);
    if(!found && adj[a].size() == 3){
        found = true;
        dsu[1].remver = a;
        for(int i = 0; i < 3; i++){
            dsu[i + 2].remver = adj[a][i];
            for(int v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
                dsu[i + 2].add(v, u);
        }
    }
    else if(adj[a].size() == 3){
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = true;
        for(int i = 1; i < 5; i++) if(!mark[dsu[i].remver])
            dsu[i].noans = true;
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = false;
    }
    else if(adj[a].size() == 4){
        for(int i = 1; i < 5; i++) if(dsu[i].remver != a)
            dsu[i].noans = true;
    }
    swap(a, b);
    if(!found && adj[a].size() == 3){
        found = true;
        dsu[1].remver = a;
        for(int i = 0; i < 3; i++){
            dsu[i + 2].remver = adj[a][i];
            for(int v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
                dsu[i + 2].add(v, u);
        }
    }
    else if(adj[a].size() == 3){
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = true;
        for(int i = 1; i < 5; i++) if(!mark[dsu[i].remver])
            dsu[i].noans = true;
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = false;
    }
    else if(adj[a].size() == 4){
        for(int i = 1; i < 5; i++) if(dsu[i].remver != a)
            dsu[i].noans = true;
    }
}

int CountCritical() {

    if(found){
        int num = 0;
        for(int i = 1; i < 5; i++) 
            num += (!dsu[i].noans);
        return num;
    }
    if(!cy)
        return n;
    if(morecy)
        return 0;
    return cynum;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47220 KB Output is correct
2 Correct 21 ms 47432 KB Output is correct
3 Correct 19 ms 47444 KB Output is correct
4 Correct 18 ms 47256 KB Output is correct
5 Correct 19 ms 47304 KB Output is correct
6 Correct 18 ms 47416 KB Output is correct
7 Correct 18 ms 47240 KB Output is correct
8 Correct 18 ms 47444 KB Output is correct
9 Correct 19 ms 47504 KB Output is correct
10 Correct 21 ms 47428 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 65076 KB Output is correct
2 Correct 865 ms 74004 KB Output is correct
3 Correct 1102 ms 77436 KB Output is correct
4 Correct 794 ms 80600 KB Output is correct
5 Correct 746 ms 84556 KB Output is correct
6 Correct 697 ms 83584 KB Output is correct
7 Correct 1010 ms 80912 KB Output is correct
8 Correct 955 ms 82552 KB Output is correct
9 Correct 997 ms 84372 KB Output is correct
10 Correct 459 ms 82712 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47220 KB Output is correct
2 Correct 21 ms 47432 KB Output is correct
3 Correct 19 ms 47444 KB Output is correct
4 Correct 18 ms 47256 KB Output is correct
5 Correct 19 ms 47304 KB Output is correct
6 Correct 18 ms 47416 KB Output is correct
7 Correct 18 ms 47240 KB Output is correct
8 Correct 18 ms 47444 KB Output is correct
9 Correct 19 ms 47504 KB Output is correct
10 Correct 21 ms 47428 KB Output is correct
11 Incorrect 26 ms 47436 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47220 KB Output is correct
2 Correct 21 ms 47432 KB Output is correct
3 Correct 19 ms 47444 KB Output is correct
4 Correct 18 ms 47256 KB Output is correct
5 Correct 19 ms 47304 KB Output is correct
6 Correct 18 ms 47416 KB Output is correct
7 Correct 18 ms 47240 KB Output is correct
8 Correct 18 ms 47444 KB Output is correct
9 Correct 19 ms 47504 KB Output is correct
10 Correct 21 ms 47428 KB Output is correct
11 Incorrect 26 ms 47436 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47220 KB Output is correct
2 Correct 21 ms 47432 KB Output is correct
3 Correct 19 ms 47444 KB Output is correct
4 Correct 18 ms 47256 KB Output is correct
5 Correct 19 ms 47304 KB Output is correct
6 Correct 18 ms 47416 KB Output is correct
7 Correct 18 ms 47240 KB Output is correct
8 Correct 18 ms 47444 KB Output is correct
9 Correct 19 ms 47504 KB Output is correct
10 Correct 21 ms 47428 KB Output is correct
11 Correct 275 ms 65076 KB Output is correct
12 Correct 865 ms 74004 KB Output is correct
13 Correct 1102 ms 77436 KB Output is correct
14 Correct 794 ms 80600 KB Output is correct
15 Correct 746 ms 84556 KB Output is correct
16 Correct 697 ms 83584 KB Output is correct
17 Correct 1010 ms 80912 KB Output is correct
18 Correct 955 ms 82552 KB Output is correct
19 Correct 997 ms 84372 KB Output is correct
20 Correct 459 ms 82712 KB Output is correct
21 Incorrect 26 ms 47436 KB Output isn't correct
22 Halted 0 ms 0 KB -