Submission #423216

#	Time	Username	Problem	Language	Result	Execution time	Memory
423216		Monchito	Split the Attractions (IOI19_split)	C++14	18 / 100	129 ms	18076 KiB

split

#include "split.h"
#include <algorithm>
using namespace std;
using vi = vector<int>;

const int MAXN = 1e5;
vi G[MAXN], CC[MAXN];
bool vis[MAXN];

void DFS(int current_node, int current_CC){
    vis[current_node] = true;
    CC[current_CC].push_back(current_node);   

    for(int v : G[current_node]){
        if(!vis[v]) DFS(v, current_CC);
    }
}

vector<int> find_split(int n, int a, int b, int c, vi p, vi q){
	vi res(n, 0);

    for(int i=0; i<(int)p.size(); i++){
        G[p[i]].push_back(q[i]);
        G[q[i]].push_back(p[i]);
    }

    int current_CC = 0;

    for(int i=0; i<n; i++){
        if(!vis[i]) { DFS(i, current_CC); current_CC++; }
    }

    pair<int,int> CC_info[current_CC], values[3] = { {a, 1}, {b, 2}, {c, 3} };
    for(int i=0; i<current_CC; i++) { CC_info[i].first = CC[i].size(); CC_info[i].second = i; }

    sort(CC_info, CC_info + current_CC);
    sort(values, values+3);

    for(int i=0; i<2; i++){
        bool can = false;

        for(int j=0; j<current_CC; j++){
            if(CC_info[j].first >= values[i].first){
                for(int z = CC_info[j].first-1; z >= CC_info[j].first - values[i].first; z--)
                    res[CC[CC_info[j].second][z]] = values[i].second;

                CC_info[j].first -= values[i].first; 
                can = true;
                break;
            }
        }

        if(!can) { res = vi(n, 0); return res; }
    }

    for(int i=0; i<current_CC; i++){
        for(int j=CC_info[i].first-1; j >= 0; j--)
            res[CC[CC_info[i].second][j]] = values[2].second;
    }

	return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36