oj.uz

Submission #1046926

# Submission time Handle Problem Language Result Execution time Memory
1046926 2024-08-07T06:21:35 Z onbert Parachute rings (IOI12_rings) C++17
0 / 100
 188 ms 89544 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5;
int n;
int fa[maxn];
int freq[maxn][4];
vector<int> adj[maxn];
int rt(int u) {
    if (fa[u]==u) return u;
    return fa[u] = rt(fa[u]);
}
void merge(int u, int v) {
    int U = rt(u), V = rt(v);
    if (U!=V) {
        for (int i=0;i<=3;i++) freq[V][i] += freq[U][i];
        fa[U] = V;
    }
    if (adj[u].size()<=3) freq[V][adj[u].size()]--;
    if (adj[v].size()<=3) freq[V][adj[v].size()]--;
    adj[u].push_back(v); adj[v].push_back(u);
    if (adj[u].size()<=3) freq[V][adj[u].size()]++;
    if (adj[v].size()<=3) freq[V][adj[v].size()]++;
}

void Init(int32_t N) {
    n = N;
    for (int i=0;i<n;i++) fa[i] = i, freq[i][0] = 1, freq[i][1] = freq[i][2] = freq[i][3] = 0;
}

vector<pair<int,int>> track;
bool die = false;
int one = -1, three = -1, deadgrp = -1;
void Link(int32_t u, int32_t v) {
    if (u==one || v==one || die) return;
    track.push_back({u, v});
    merge(u, v);
    if (three==-1 && adj[u].size()==3) three = u;
    if (three==-1 && adj[v].size()==3) three = v;
    int U = rt(u);
    if (freq[U][1]!=2 || freq[U][3]!=0) {
        if (one!=-1 || (deadgrp!=-1 && rt(deadgrp)!=U)) {die = true; return;}
        deadgrp = U;
    }
    if (one==-1 && adj[u].size()==4 || adj[v].size()==4) {
        if (adj[v].size()==4) swap(u, v);
        one = u;
        for (int i=0;i<n;i++) fa[i] = i, freq[i][0] = 1, freq[i][1] = freq[i][2] = freq[i][3] = 0;
        for (auto [u, v]:track) Link(u, v);
    }
}

int32_t CountCritical() {
    if (die) return 0;
    if (one!=-1) return 1;
    if (three!=-1) {
        // cout << "test " << three << endl;
        vector<int> vec = adj[three];
        vec.push_back(three);
        int ans = 0, U = rt(three);
        // cout << "test3 " << freq[U][0] << " " << freq[U][1] << " " << freq[U][2] << " " << freq[U][3] << endl;
        for (int u:vec) {
            for (int v:adj[u]) {
                int sz = adj[v].size();
                freq[U][sz]--;
                freq[U][sz-1]++;
            }
            freq[U][adj[u].size()]--;
            // cout << "test2 " << u << " " << freq[U][0] << " " << freq[U][1] << " " << freq[U][2] << " " << freq[U][3] << endl;
            if (freq[U][3]==0 && freq[U][1]>=2) {
                ans++;
            }
            for (int v:adj[u]) {
                int sz = adj[v].size();
                freq[U][sz]++;
                freq[U][sz-1]--;
            }
            freq[U][adj[u].size()]++;
        }
        return ans;
    }
    return n;
}

Compilation message

rings.cpp: In function 'void Link(int32_t, int32_t)':
rings.cpp:45:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   45 |     if (one==-1 && adj[u].size()==4 || adj[v].size()==4) {
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27224 KB Output is correct
2 Incorrect 4 ms 27480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 78920 KB Output is correct
2 Incorrect 188 ms 89544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27224 KB Output is correct
2 Incorrect 4 ms 27480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27224 KB Output is correct
2 Incorrect 4 ms 27480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27224 KB Output is correct
2 Incorrect 4 ms 27480 KB Output isn't correct
3 Halted 0 ms 0 KB -