제출 #568326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568326		cheissmart	낙하산 고리들 (IOI12_rings)	C++14	컴파일 에러	0 ms	0 KiB

rings

#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 7, MAGIC = INF;

int n;
int p[N], sz[N], esz[N];
bool not_in[N];
vi G[N], g[N], s;

void Init(int _n) {
    n = _n;
    for(int i = 0; i < n; i++) {
        p[i] = i;
        sz[i] = 1;
        s.PB(i);
    }
}

int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}

void unite(int u, int v) {
    u = find(u), v = find(v);
    assert(u != v);
    if(sz[u] > sz[v]) swap(u, v);
    p[u] = v;
    sz[v] += sz[u];
    esz[v] += esz[u];
}

V<pi> tt;
int cc = 0, bad_cnt = 0;

void inter(vi ss) {
    vi tmp;
    for(int u:s) if(find(ALL(ss), u) != ss.end())
        tmp.PB(u);
    swap(tmp, s);
}

void check(int u) {
    if(SZ(g[u]) <= 2) return;
    bad_cnt++;
    if(SZ(g[u]) > 3)
        inter({u});
    inter({u, g[u][0], g[u][1], g[u][2]});
}

void Link(int u, int v) {
    if(find(u) != find(v)) {
        if(esz[find(u)] >= sz[find(u)]) cc--;
        if(esz[find(v)] >= sz[find(v)]) cc--;
        unite(u, v);
        if(esz[find(u)] >= sz[find(u)]) cc++;
        G[u].PB(v);
        G[v].PB(u);
    } else {
        if(esz[find(u)] >= sz[find(u)]) cc--;
        esz[find(u)]++;
        if(esz[find(u)] >= sz[find(u)]) cc++;

        tt.EB(u, v);
        if(SZ(tt) <= MAGIC) {
            vi stk;
            vi vis(n);
            function<void(int, int)> dfs = [&] (int x, int pa) {
                stk.PB(x);
                if(x == v) {
                    for(int i:stk) vis[i] = 1;
                }
                for(int y:G[x]) if(y != pa) {
                    dfs(y, x);
                }
                stk.pop_back();
            };
            for(int i = 0; i < n; i++) if(!vis[i])
                not_in[i] = true;
        } 
    }
    g[u].PB(v);
    g[v].PB(u);
    check(u), check(v);
}

bool ok(int u) {
    if(SZ(tt) >= MAGIC) return false;
    if(not_in[u]) return false;
    return true;
}

int CountCritical() {
    if(cc > 1) return 0;
    if(s.empty()) return 0;
    if(cc == 0) return SZ(s);
    if(esz[find(s[0])] < sz[find(s[0])]) return 0;
    if(bad_cnt == 1) {
    //     if(SZ(s) == 1) return 1;
    //     return 3;
    // }
    int ans = 0;
    for(int u:s)
        if(ok(u)) ans++;
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

rings.cpp: In function 'int CountCritical()':
rings.cpp:120:1: error: expected '}' at end of input
  120 | }
      | ^
rings.cpp:107:21: note: to match this '{'
  107 | int CountCritical() {
      |                     ^
rings.cpp:120:1: warning: control reaches end of non-void function [-Wreturn-type]
  120 | }
      | ^