Submission #233210

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

split

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

using namespace std;


vector<int> adj[100005];
int children[100005];
bool visited[100005];
vector<int> adj2[100005];
int ans[100005];
int mark;
int sz;
bool ok;
int doo;
int nn;

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

    for (int i : adj[v]){
        if (visited[i] == false){
            dfs(i);
            children[v]+= children[i];
            adj2[v].push_back(i);
        }
    }

    children[v]++;

    if ((children[v] >= sz)&&(ok == false)&&(nn - children[v] > sz)){
        doo = v;
        ok = true;
    }

}



void dfs2(int v){
    visited[v] = true;
    ans[v] = mark;

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

}


vector<int> comp;


void dfs3(int v){
    visited[v] = true;
    comp.push_back(v);

    for (int i : adj[v]){
        if (visited[i] == false){
            dfs3(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;
    nn = n;
    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);
    }


    doo = -1;
    ok = false;
    mark = abc[0].second;
    sz = abc[0].first;


    dfs(0);

    if (doo == -1){
        vector<int> emptyy(n,0);
        return emptyy;
    }

    memset(visited , false , sizeof visited);
    sz--;
    dfs2(doo);

//    cout << "this is res :  " ;
//    for (int i = 0 ; i < 10 ; i++){
//        cout << ans[i] << " ";
//    }

//    cout << endl;



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

    for (int i = 0 ; i < n ; i++){
        if (visited[i] == false){
            dfs3(i);
            if (comp.size() >= sz){
                        for (int i = 0 ; i < sz ; i++){
            ans[comp[i]] = mark;
        }

        mark = abc[2].second;

        for (int i = 0 ; i < n ; i++){
            res[i] = (ans[i] == 0 ? mark : ans[i]);
        }

        return res;

            }
            else comp.clear();
        }
    }

    vector<int> emptyy(n,0);

    return emptyy;


}

Compilation message (stderr)

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

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