제출 #382342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382342		ParsaAlizadeh	낙하산 고리들 (IOI12_rings)	C++17	20 / 100	18 ms	1004 KiB

rings

#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
#define endl            '\n'

constexpr ll pw(ll a, ll b, ll mod) {
    return (!b    ? 1 :
            b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
                    pw(a * a % mod, b / 2, mod));
}

constexpr int N   = 5e3 + 10;
constexpr int MOD = 1e9 + 7;
constexpr ll INF  = 1e18;

int n, mark[N], par[N], edg[N], sz[N];
vector<int> adj[N];

bool critDFS(int u) {
    int d = 0;
    bool flag = true;
    mark[u] = 1;
    for (int v : adj[u]) if (mark[v] < 3) {
        d++;
        flag &= (mark[v] != 2);
        if (mark[v] == 0) {
            flag &= critDFS(v);
        }
    }
    flag &= (d <= 2);
    mark[u] = 2;
    return flag;
}

bool check(int u) {
    bool flag = true;
    fill(mark, mark + N, 0);
    mark[u] = 3;
    for (int i = 0; i < n; i++) if (mark[i] == 0) {
        flag &= critDFS(i);
    }
    return flag;
}

int dsufind(int u) {
    return (par[u] == -1 ? u : par[u] = dsufind(par[u]));
}

void dsumerge(int u, int v) {
    u = dsufind(u), v = dsufind(v);
    if (u == v) {
        edg[u]++;
        return;
    }
    if (sz[v] > sz[u])
        swap(u, v);
    par[v] = u;
    edg[u] += edg[v] + 1;
    sz[u] += sz[v];
}

void Init(int N_) {
    n = N_;
    assert(n < N);
    fill(par, par + n, -1);
    fill(sz, sz + n, 1);
}

void Link(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);

    dsumerge(u, v);
}

int CountCritical() {
    vector<int> v3, v4;
    for (int i = 0; i < n; i++) {
        if (adj[i].size() >= 4)
            v4.push_back(i);
        else if (adj[i].size() == 3)
            v3.push_back(i);
    }
    if (v4.size() >= 2)
        return 0;
    if (v4.size() == 1)
        return check(v4[0]);
    if (v3.size() >= 1) {
        int ans = check(v3[0]);
        for (int v : adj[v3[0]])
            ans += check(v);
        return ans;
    }
    int t[2] = {0, 0};
    for (int i = 0; i < n; i++) if (dsufind(i) == i) {
        if (edg[i] == sz[i]) {
            if (t[1] > 0) return 0;
            t[1] = sz[i];
        }
        else
            t[0] += sz[i];
    }
    return (t[1] > 0 ? t[1] : t[0]);
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31