제출 #442382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442382		AmineTrabelsi	Split the Attractions (IOI19_split)	C++14	18 / 100	116 ms	16520 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int Mx = 2e5+5;
int N,M;
vector<int> order;
vector<int> gr[Mx];
bool vis[Mx];
void get_order(int node){
    vis[node] = 1;
    order.push_back(node);
    for(auto i:gr[node]){
        if(!vis[i])
        get_order(i);
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    // subtask 1
    N = n;
    M = p.size();
    for(int i=0;i<M;i++){
        gr[p[i]].push_back(q[i]);
        gr[q[i]].push_back(p[i]);
    }
    vector<int> res(N,0);
    bool done = 0;
    for(int i=0;i<n;i++){
        if(gr[i].size() == 1){
            get_order(i);
            done = 1;
        }
    }
    if(!done)get_order(0); // cycle
    for(int i=0;i<a;i++){
        res[order[i]] = 1;
    }
    for(int i=0;i<b;i++){
        res[order[i+a]] = 2;
    }
    for(int i=0;i<c;i++){
        res[order[i+a+b]] = 3;
    }
    return res;
}

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