oj.uz

Submission #544953

# Submission time Handle Problem Language Result Execution time Memory
544953 2022-04-03T08:21:41 Z tabr Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 43928 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int n;
vector<vector<int>> g;
vector<int> deg;

void Init(int n_) {
    n = n_;
    g = vector<vector<int>>(n);
    deg = vector<int>(n);
}

void Link(int x, int y) {
    g[x].emplace_back(y);
    g[y].emplace_back(x);
    deg[x]++;
    deg[y]++;
}

struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p = vector<int>(n);
        iota(p.begin(), p.end(), 0);
        sz = vector<int>(n, 1);
    }

    inline int get(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }

    inline bool same(int x, int y) {
        return (get(x) == get(y));
    }

    inline int size(int x) {
        return sz[get(x)];
    }

    inline bool root(int x) {
        return (x == get(x));
    }
};

bool check(int v) {
    dsu uf(n);
    vector<int> new_deg(n);
    for (int i = 0; i < n; i++) {
        for (int j : g[i]) {
            if (i == v || j == v || i > j) {
                continue;
            }
            if (!uf.unite(i, j)) {
                return false;
            }
            new_deg[i]++;
            new_deg[j]++;
        }
    }
    if (*max_element(new_deg.begin(), new_deg.end()) > 2) {
        return false;
    }
    return true;
}

int CountCritical() {
    int mx = *max_element(deg.begin(), deg.end());
    int v = (int) (max_element(deg.begin(), deg.end()) - deg.begin());
    int ans = 0;
    if (mx >= 4) {
        ans += check(v);
    } else if (mx == 3) {
        ans += check(v);
        for (int to : g[v]) {
            ans += check(to);
        }
    } else {
        for (int i = 0; i < n; i++) {
            ans += check(i);
        }
    }
    return ans;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Init(7);
    cout << CountCritical() << endl;  // 7
    Link(1, 2);
    cout << CountCritical() << endl;  // 7
    Link(0, 5);
    cout << CountCritical() << endl;  // 7
    Link(2, 0);
    cout << CountCritical() << endl;  // 7
    Link(3, 2);
    cout << CountCritical() << endl;  // 4
    Link(3, 5);
    cout << CountCritical() << endl;  // 3
    Link(4, 3);
    cout << CountCritical() << endl;  // 2
    return 0;
}
#endif

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 18 ms 384 KB Output is correct
5 Correct 201 ms 544 KB Output is correct
6 Correct 658 ms 728 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 364 ms 636 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 4 ms 660 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 18 ms 384 KB Output is correct
5 Correct 201 ms 544 KB Output is correct
6 Correct 658 ms 728 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 364 ms 636 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 4 ms 660 KB Output is correct
11 Execution timed out 4086 ms 596 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 18 ms 384 KB Output is correct
5 Correct 201 ms 544 KB Output is correct
6 Correct 658 ms 728 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 364 ms 636 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 4 ms 660 KB Output is correct
11 Execution timed out 4086 ms 596 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 18 ms 384 KB Output is correct
5 Correct 201 ms 544 KB Output is correct
6 Correct 658 ms 728 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 364 ms 636 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 4 ms 660 KB Output is correct
11 Execution timed out 4074 ms 43928 KB Time limit exceeded
12 Halted 0 ms 0 KB -