Submission #841595

#	Time	Username	Problem	Language	Result	Execution time	Memory
841595		Alfraganus	Split the Attractions (IOI19_split)	C++17	18 / 100	54 ms	12868 KiB

split

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

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
    bool sb1 = true;
    int m = p.size();
    vector<vector<int>> graph(n);
    vector<int> cnt(n);
    for(int i = 0; i < m; i ++){
        graph[p[i]].push_back(q[i]);
        graph[q[i]].push_back(p[i]);
        cnt[p[i]] ++;
        cnt[q[i]] ++;
    }
    for(int i = 0; i < n; i ++){
        if(cnt[i] > 2)
            sb1 = false;
    }
    vector<int> ans(n);
    if(sb1){
        int root = 0;
        for(int i = 0; i < n; i ++){
            if(cnt[i] == 1){
                root = i;
                break;
            }
        }
        queue<int> q;
        int k = 1;
        vector<bool> used(n);
        q.push(root);
        used[root] = true;
        ans[root] = 1;
        while(!q.empty()){
            int x = q.front();
            q.pop();
            
            for(auto neighbour : graph[x]){
                if(!used[neighbour]){
                    used[neighbour] = true;
                    q.push(neighbour);
                    if(k < a)
                        ans[neighbour] = 1;
                    else if(k < a + b)
                        ans[neighbour] = 2;
                    else
                        ans[neighbour] = 3;
                    k ++;
                }
            }
        }
        return ans;
    }
    else if(a == 1){
        queue<int> q;
        q.push(0);
        vector<bool> used(n);
        int k = 1;
        ans[0] = 2;
        used[0] = true;
        while(k < b){
            int x = q.front();
            q.pop();
            
            for(auto neighbour : graph[x]){
                if(!used[neighbour] and k < b){
                    ans[neighbour] = 2;
                    q.push(neighbour);
                    k ++;
                    used[neighbour] = true;
                }
            }
        }
        for(int i = 0; i < n; i ++){
            if(ans[i] == 0){
                ans[i] = 1;
                break;
            }
        }
        for(int i = 0; i < n; i ++){
            if(ans[i] == 0){
                ans[i] = 3;
            }
        }
        return ans;
    }
    else{
        return ans;
    }
}

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