답안 #281901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
281901	2020-08-23T15:29:09 Z	hoanghq2004	Split the Attractions (IOI19_split)	C++14	컴파일 오류	0 ms	0 KB

split

#include <bits/stdc++.h>

#define F0R(i, a) for (int i = 0; i < (a); ++i)

#define sz(x) (int)((x).size())

#define PB push_back
#define MP make_pair
#define F first
#define S second

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;

#define MAXN 100000

int n, m, ss[MAXN], depth[MAXN], low[MAXN];
bool vis[MAXN];
vector<pii> options;
int color[MAXN];
vi adj[MAXN];

void dfs(int node) {
    vis[node] = 1;
    ss[node] = 1;
    low[node] = depth[node];
    for (const int next : adj[node]) {
        if (!vis[next]) {
            depth[next] = depth[node] + 1;
            dfs(next);
            ss[node] += ss[next];
            low[node] = min(low[node], low[next]);
        } else {
            low[node] = min(low[node], depth[next]);
        }
    }
}

int dfs2(int node) {
    for (const int next : adj[node]) {
        if (depth[next] == depth[node] + 1) {
            if (ss[next] >= options[0].F) {
                return dfs2(next);
            }
        }
    }
    return node;
}

void floodfill(int node, int& cnt, int col, int restriction = 100000) {
    if (cnt == 0) {
        return;
    }
    color[node] = col;
    cnt--;
    for (const int next : adj[node]) {
        if (abs(depth[next] - depth[node]) <= restriction && color[next] == 0) {
            floodfill(next, cnt, col, restriction);
        }
    }
}

vi find_split(int _n, int a, int b, int c, vi p, vi q) {
    n = _n;
    options.PB(MP(a, 1));
    options.PB(MP(b, 2));
    options.PB(MP(c, 3));
    sort(all(options));
    m = sz(p);
    F0R(i, m) {
        adj[p[i]].PB(q[i]);
        adj[q[i]].PB(p[i]);
    }
    dfs(0);
    int v = dfs2(0);
    
    int p1 = ss[v];
    vi children, nonchildren;
    for (const int u : adj[v]) {
        if (depth[u] == depth[v] + 1) {
            if (p1 - ss[u] >= options[0].F && low[u] < depth[v]) {
                p1 -= ss[u];
                nonchildren.PB(u);
            } else {
                children.PB(u);
            }
        } else {
            nonchildren.PB(u);
        }
    }
    int p2 = n - p1;
    if (p1 >= options[0].F && p2 >= options[1].F) {
        color[v] = options[0].S;
        options[0].F--;
        for (const int next : children) {
            floodfill(next, options[0].F, options[0].S, 1);
        }
        if (!nonchildren.empty()) {
            floodfill(nonchildren[0], options[1].F, options[1].S);
        }
        F0R(i, n) if (color[i] == 0) {
            color[i] = options[2].S;
        }
    } else if (p1 >= options[1].F && p2 >= options[0].F) {
        color[v] = options[1].S;
        options[1].F--;
        for (const int next : children) {
            floodfill(next, options[1].F, options[1].S, 1);
        }
        if (!nonchildren.empty()) {
            floodfill(nonchildren[0], options[0].F, options[0].S);
        }
        F0R(i, n) if (color[i] == 0) {
            color[i] = options[2].S;
        }
    }
    
    vi res;
    F0R(i, n) res.PB(color[i]);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, a, b, c;
    cin >> n >> m;
    cin >> a >> b >> c;
    vi p, q;
    F0R(i, m) {
        int u, v;
        cin >> u >> v;
        p.PB(u);
        q.PB(v);
    }
    vi res = find_split(n, a, b, c, p, q);
    for (const int i : res) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

Compilation message

/tmp/cch5sJWX.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccliyEsG.o:split.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status