oj.uz

Submission #658122

# Submission time Handle Problem Language Result Execution time Memory
658122 2022-11-12T08:07:18 Z jiahng Parachute rings (IOI12_rings) C++14
69 / 100
 4000 ms 171204 KB 
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
 
typedef long long ll;
#define ll int
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 1000010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int N;
int d[maxn], maxD;
vi st[maxn], adj[maxn],cycles[6];
vpi all_edges;
int p[6][maxn], edges[6][maxn], sz[6][maxn], ncycles[6];
vi pos;
int fl(int i, int x){
    if (p[i][x] == x) return x;
    return p[i][x] = fl(i, p[i][x]);
}
 
void add(int i, int A, int B){
    if (sz[fl(i,A)] > sz[fl(i,B)]) swap(A,B);
    
    if (fl(i, A) != fl(i,B)){
        int pA = fl(i,A), pB = fl(i,B);
        if (edges[i][pA] >= sz[i][pA]) ncycles[i]--;
        if (edges[i][pB] >= sz[i][pB]) ncycles[i]--;
        sz[i][pB] += sz[i][pA];
        edges[i][pB] += edges[i][pA];
        p[i][pA] = pB;
    }else if (edges[i][fl(i,A)] >= sz[i][fl(i,A)]) ncycles[i]--;
    edges[i][fl(i,B)]++;
    if (edges[i][fl(i,B)] >= sz[i][fl(i,B)]){
        ncycles[i]++; cycles[i].pb(fl(i,B));
    }
}
int bigx;
int gt3 = 0;

void Init(int N_) {
    N = N_;
    maxD = 0;
    FOR(i,0,5) FOR(j,0,N-1) p[i][j] = j,sz[i][j] = 1;
    bigx = -1;
}
void Link(int A, int B) {
    if (d[A] == 3) gt3++;
    if (d[B] == 3) gt3++;
    d[A]++; d[B]++;
    st[d[A]].pb(A); st[d[B]].pb(B);
 
    adj[A].pb(B); adj[B].pb(A);
 
    if (pos.empty() && (d[A] == 3 || d[B] == 3)){
        if (d[A] == 3){
            aFOR(i, adj[A]) pos.pb(i);
            pos.pb(A);
        }else if (d[B] == 3){
            pos.pb(B); aFOR(i, adj[B]) pos.pb(i);
        }
        FOR(i,0,pos.size()-1){
            aFOR(j, all_edges) if (j.f != pos[i] && j.s != pos[i]) add(i,j.f,j.s);
        }
    }
    all_edges.pb(pi(A,B));
    maxD = max({maxD, d[A], d[B]});
 
    add(5,A,B);
    FOR(i,0,(int)pos.size()-1) if (A != pos[i] && B != pos[i]) add(i,A,B);
}
 
int CountCritical() {
    if (N == 1) return 1;
    if (maxD >= 4){
        if (gt3 > 1) return 0;
        if (st[maxD].size() == 1){
            int x = st[maxD][0];
            bool no = 0;
            if (find(all(pos),x) == pos.end()) return 0;
            int idx = find(all(pos), x) - pos.begin();
            if (!cycles[idx].empty()) return 0;
            aFOR(i, st[3]) if (i != x && find(all(adj[i]), x) == adj[i].end()) return 0;
            return 1;
        }else return 0;
    }else if (maxD <= 1) return N;
    else if (maxD == 3){
        if (st[3].size() > 4) return 0;
       
        int ans = 0;
        FOR(i,0,pos.size()-1){
            bool no = 0;
            aFOR(j, st[3]) if (pos[i] != j && find(all(adj[j]), pos[i]) == adj[j].end()){
                no = 1; break;
            }
            if (no) continue;
            if (cycles[i].empty()){
                //cout << "! " << i << '\n';
                ans++;
            }
        }
        return ans;
    }else{
        if (ncycles[5] == 0) return N;
        else if (ncycles[5] == 1) return sz[5][fl(5,cycles[5][0])];
        else return 0;
    }
}

Compilation message

rings.cpp: In function 'int CountCritical()':
rings.cpp:99:18: warning: unused variable 'no' [-Wunused-variable]
   99 |             bool no = 0;
      |                  ^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 25 ms 47932 KB Output is correct
3 Correct 25 ms 48080 KB Output is correct
4 Correct 22 ms 47432 KB Output is correct
5 Correct 25 ms 47680 KB Output is correct
6 Correct 33 ms 47924 KB Output is correct
7 Correct 27 ms 47756 KB Output is correct
8 Correct 26 ms 47752 KB Output is correct
9 Correct 27 ms 48092 KB Output is correct
10 Correct 26 ms 48060 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 100076 KB Output is correct
2 Correct 1716 ms 142308 KB Output is correct
3 Correct 2111 ms 171204 KB Output is correct
4 Correct 1293 ms 149084 KB Output is correct
5 Correct 1243 ms 148968 KB Output is correct
6 Correct 1240 ms 147148 KB Output is correct
7 Correct 1982 ms 170044 KB Output is correct
8 Correct 1874 ms 157220 KB Output is correct
9 Correct 1912 ms 164608 KB Output is correct
10 Correct 912 ms 142920 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 25 ms 47932 KB Output is correct
3 Correct 25 ms 48080 KB Output is correct
4 Correct 22 ms 47432 KB Output is correct
5 Correct 25 ms 47680 KB Output is correct
6 Correct 33 ms 47924 KB Output is correct
7 Correct 27 ms 47756 KB Output is correct
8 Correct 26 ms 47752 KB Output is correct
9 Correct 27 ms 48092 KB Output is correct
10 Correct 26 ms 48060 KB Output is correct
11 Correct 25 ms 47956 KB Output is correct
12 Correct 27 ms 48620 KB Output is correct
13 Correct 30 ms 48696 KB Output is correct
14 Correct 28 ms 48580 KB Output is correct
15 Correct 29 ms 49248 KB Output is correct
16 Correct 28 ms 48456 KB Output is correct
17 Correct 30 ms 48852 KB Output is correct
18 Correct 31 ms 49428 KB Output is correct
19 Correct 28 ms 48508 KB Output is correct
20 Correct 29 ms 48712 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 25 ms 47932 KB Output is correct
3 Correct 25 ms 48080 KB Output is correct
4 Correct 22 ms 47432 KB Output is correct
5 Correct 25 ms 47680 KB Output is correct
6 Correct 33 ms 47924 KB Output is correct
7 Correct 27 ms 47756 KB Output is correct
8 Correct 26 ms 47752 KB Output is correct
9 Correct 27 ms 48092 KB Output is correct
10 Correct 26 ms 48060 KB Output is correct
11 Correct 25 ms 47956 KB Output is correct
12 Correct 27 ms 48620 KB Output is correct
13 Correct 30 ms 48696 KB Output is correct
14 Correct 28 ms 48580 KB Output is correct
15 Correct 29 ms 49248 KB Output is correct
16 Correct 28 ms 48456 KB Output is correct
17 Correct 30 ms 48852 KB Output is correct
18 Correct 31 ms 49428 KB Output is correct
19 Correct 28 ms 48508 KB Output is correct
20 Correct 29 ms 48712 KB Output is correct
21 Correct 42 ms 51476 KB Output is correct
22 Correct 51 ms 53948 KB Output is correct
23 Correct 58 ms 55732 KB Output is correct
24 Correct 2237 ms 57356 KB Output is correct
25 Correct 467 ms 54880 KB Output is correct
26 Correct 106 ms 55964 KB Output is correct
27 Correct 77 ms 56000 KB Output is correct
28 Correct 100 ms 59048 KB Output is correct
29 Correct 76 ms 56556 KB Output is correct
30 Correct 78 ms 57488 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 25 ms 47932 KB Output is correct
3 Correct 25 ms 48080 KB Output is correct
4 Correct 22 ms 47432 KB Output is correct
5 Correct 25 ms 47680 KB Output is correct
6 Correct 33 ms 47924 KB Output is correct
7 Correct 27 ms 47756 KB Output is correct
8 Correct 26 ms 47752 KB Output is correct
9 Correct 27 ms 48092 KB Output is correct
10 Correct 26 ms 48060 KB Output is correct
11 Correct 500 ms 100076 KB Output is correct
12 Correct 1716 ms 142308 KB Output is correct
13 Correct 2111 ms 171204 KB Output is correct
14 Correct 1293 ms 149084 KB Output is correct
15 Correct 1243 ms 148968 KB Output is correct
16 Correct 1240 ms 147148 KB Output is correct
17 Correct 1982 ms 170044 KB Output is correct
18 Correct 1874 ms 157220 KB Output is correct
19 Correct 1912 ms 164608 KB Output is correct
20 Correct 912 ms 142920 KB Output is correct
21 Correct 25 ms 47956 KB Output is correct
22 Correct 27 ms 48620 KB Output is correct
23 Correct 30 ms 48696 KB Output is correct
24 Correct 28 ms 48580 KB Output is correct
25 Correct 29 ms 49248 KB Output is correct
26 Correct 28 ms 48456 KB Output is correct
27 Correct 30 ms 48852 KB Output is correct
28 Correct 31 ms 49428 KB Output is correct
29 Correct 28 ms 48508 KB Output is correct
30 Correct 29 ms 48712 KB Output is correct
31 Correct 42 ms 51476 KB Output is correct
32 Correct 51 ms 53948 KB Output is correct
33 Correct 58 ms 55732 KB Output is correct
34 Correct 2237 ms 57356 KB Output is correct
35 Correct 467 ms 54880 KB Output is correct
36 Correct 106 ms 55964 KB Output is correct
37 Correct 77 ms 56000 KB Output is correct
38 Correct 100 ms 59048 KB Output is correct
39 Correct 76 ms 56556 KB Output is correct
40 Correct 78 ms 57488 KB Output is correct
41 Correct 248 ms 86324 KB Output is correct
42 Correct 730 ms 127000 KB Output is correct
43 Execution timed out 4051 ms 115860 KB Time limit exceeded
44 Halted 0 ms 0 KB -