Submission #232723

#	Time	Username	Problem	Language	Result	Execution time	Memory
232723		UserIsUndefined	Split the Attractions (IOI19_split)	C++14	18 / 100	532 ms	24824 KiB

split

#include <bits/stdc++.h>
#include "split.h"

using namespace std;


vector<int> adj[100005];


map<int,int> visited;
int children[100005];
int timein[100005];
int timeout[100005];
int timee;

int ans[100005];
int sett, sz;

int F , maxx;


void getF(int v , int p){
    visited[v] = true;
    if (p > maxx){
        p = maxx;
        F = v;
    }

    for (int i : adj[v]){
        if (visited[i] == false){
            getF(i , p + 1);
        }
    }


}



void go(int v){
    visited[v] = true;
    timee++;
    timein[v] = timee;

    for (int i : adj[v]){
        if (visited[i] == false){
            go(i);
            children[v] += children[i];
        }
    }
    timee++;
    timeout[v] = timee;
    children[v]++;


}












void dfs(int v){
    visited[v] = true;
    ans[v] = sett;

    for (int i : adj[v]){
        if ((visited[i] == false)&&(sz)){
            sz--;
            dfs(i);
        }
    }

}




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

    abc.push_back({a, 1});
    abc.push_back({b, 2});
    abc.push_back({c, 3});

    sort(abc.begin() , abc.end());


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

    F = 0;
    maxx = 0;

    getF(0 , 0);


//    cout << "first away ? :" << F <<endl;

    visited.clear();

    maxx = 0;

    getF(F, 0);
//
//    cout << "second away ? :" << F <<endl;

    visited.clear();

    go(F);

    visited.clear();

    sett = abc[0].second;
    sz = abc[0].first;
    int minn = 1e9;
    int indx = -1;

    for (int i = 0 ; i < n ; i++){
        if (children[i] >= sz){
            if (children[i] < minn){
                minn = children[i];
                indx = i;
            }
        }
    }


    int cont = 0;

    for (int i = 0 ; i < n ; i++){
        if ((timein[i] >= timein[indx])&&(timeout[i] <= timeout[indx])){
            visited[i] = true;
            res[i] = sett;
            cont++;
        }
        if (cont == sz)break;
    }




    sett = abc[1].second;
    sz = abc[1].first;

    for (int i = 0 ; i < n ; i++){
        if (visited[i] == false){
            sz--;
            dfs(i);
            if (sz == 0)break;
            else sz = abc[1].second;
        }
    }

    for (int i = 0 ; i < n ; i++){
        if (res[i] == 0)res[i] = (ans[i] == 0 ? abc[2].second : ans[i]);
    }


    map<int,int> should;
    for (int i = 0 ; i < 3 ; i++){
        should[abc[i].second] = abc[i].first;
    }

    map<int,int> ex;

    for (int i = 0 ; i < n ; i++){
        ex[res[i]]++;
    }
/*
    for (int i = 1 ; i <= 3;i++){
        if (ex[i] != should[i]){
            vector<int> empy(n,0);
            return empy;
        }
    }
*/

    return res;


}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:96:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0 ; i < p.size() ; i++){
                      ~~^~~~~~~~~~

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