Submission #233218

#	Time	Username	Problem	Language	Result	Execution time	Memory
233218		UserIsUndefined	Split the Attractions (IOI19_split)	C++14	11 / 100	2086 ms	103364 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 sz;
bool ok;
int doo;
int nn;
int now;


void mark(int v){
    ans[v] = now;

    for (int i : adj[v]){
        if ((ans[i] == 0)&&(sz)){
            sz--;
            mark(i);
        }
    }

}



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

    children[v]++;



}






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);
    }



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

        int sizex = 0 ; int sizey = 0;

        visited[x] = true;
        visited[y] = true;

        sz = 0;
        dfs(x);
        sizex = sz;
        sizey = n - sz;
        memset(visited , 0 , sizeof visited);
        if (sizex > sizey){swap(sizex , sizey); swap(x , y);}

        if ((sizex >= abc[0].first)&&(sizey >= abc[1].first)){
            now = abc[0].second;
            sz = abc[0].first;

            ans[x] = now;
            ans[y] = abc[1].second;
            sz--;

            mark(x);

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

            sz--;

            mark(y);

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

            return res;


        }


    }

    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:66:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0 ; i < p.size() ; i++){
                      ~~^~~~~~~~~~
split.cpp:75:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0 ; i < p.size() ; i++){
                      ~~^~~~~~~~~~

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