제출 #1237371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237371		jer033	Split the Attractions (IOI19_split)	C++20	컴파일 에러	0 ms	0 KiB

split

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

int centroid_find(int n, vector<vector<int>> (&edges))
{
    //create a spanning tree
    //vector<vector<int>> new_edges(n);
    vector<int> parent(n, -2);
    vector<int> nodes;

    nodes.push_back(0);
    parent[0] = -1;
    
    int curr = 0;
    int total = 1;

    while (curr < total)
    {
        int x = nodes[curr]; curr++;
        for (int y: edges[x])
        {
            if (parent[y] == -2)
            {
                parent[y] = x;
                nodes.push_back(y);
                total++;
                //new_edges[]
            }
        }
    }

    vector<int> subtreesize(n, 1);
    for (int i=n-1; i>0; i--)
    {
        int x = nodes[i];
        subtreesize[parent[x]] += subtreesize[x];
    }

    //now identify the centroid
    int bes = n+1;
    int cap = (n+1)/2;
    int centroid = -1;
    for (int i=0; i<n; i++)
        if ((subtreesize[i]<bes) and (subtreesize[i]>=cap))
        {
            bes = subtreesize[i];
            centroid = i;
        }
    return centroid;
}

vector<int> find_split_wlog(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<vector<int>> edges(n);
    int e = p.size();
    for (int i=0; i<e; i++)
    {
        int pp = p[i];
        int qq = q[i];
        edges[pp].push_back(qq);
        edges[qq].push_back(pp);
    }

    int root = centroid_find(n, edges);
    //cout << root << '\n';

    //step 3: perform a dfs and identify whether its possible or not

    vector<int> parent(n, -2);
    stack<pair<int, int>> nodes;
    vector<int> push_order;
    vector<vector<int>> children(n);

    parent[root] = -1;
    nodes.push({root, 0});
    push_order.push_back(root);

    while (!nodes.empty())
    {
        pair<int, int> info = nodes.top();
        int x = info.first; int y = info.second;
        nodes.pop();
        if ((y+1)<edges[x].size())
            nodes.push({x, y+1});
        int z = edges[x][y];
        if (parent[z]==-2)
        {
            parent[z] = x;
            nodes.push({z, 0});
            push_order.push_back(z);
            children[x].push_back(z);
        }
    }

    vector<int> subtreesize(n, 1);
    for (int i=n-1; i>0; i--)
    {
        int x = push_order[i];
        subtreesize[parent[x]] += subtreesize[x];
        //cout << x << subtreesize[x] << '\n';
    }
    
    int node_min = n+1;
    int root_a = -1;
    for (int i: edges[root])
        if ((i!=root) and (subtreesize[i] < node_min) and (subtreesize[i]>=a))
        {
            node_min = subtreesize[i];
            root_a = i;
        }
    
    if (root_a == -1)
    {
        vector<int> ans(n, 0);
        return ans;
    }

    //then a solution is possible
    vector<int> ans(n, 3);
    queue<int> group_a;
    group_a.push(root_a);
    ans[root_a] = 1;
    int members = 1;
    while (members < a)
    {
        int x = group_a.front(); group_a.pop();
        for (int y: children[x])
            if (members < a)
            {
                ans[y] = 1;
                group_a.push(y);
                members++;
            }
    }

    queue<int> group_b;
    group_b.push(root);
    ans[root] = 2;
    members = 1;
    while (members < b)
    {
        int x = group_b.front(); group_b.pop();
        for (int y: children[x])
            if ((members < b) and (ans[y]==3))
            {
                ans[y] = 2;
                group_b.push(y);
                members++;
            }
    }

    return ans;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> rewrite = {0, 1, 2, 3};
    for (int i=0; i<5; i++)
    {
        if (a>b)
        {
            swap(a, b);
            swap(rewrite[1], rewrite[2]);
        }
        if (b>c)
        {
            swap(b, c);
            swap(rewrite[2], rewrite[3]);
        }
    }

    vector<int> ans = find_split_wlog(n, a, b, c, p, q);
    for (int i=0; i<n; i++)
    {
        ans[i] = rewrite[ans[i]];
    }
    return ans;
}

int main() {
	int n, m, a, b, c; cin >> n >> m >> a >> b >> c;
	vector<int> p(m), q(m);
	for (int i=0; i<m; i++)
		cin >> p[i] >> q[i];

	vector<int> result = find_split(n, a, b, c, p, q);

	for (int i=0; i<(int)result.size(); i++)
		printf("%s%d", ((i>0)?" ":""), result[i]);
	printf("\n");

	return 0;
}

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

/usr/bin/ld: /tmp/ccOqkgks.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccdbDtV8.o:split.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status