Submission #260659

#	Time	Username	Problem	Language	Result	Execution time	Memory
260659		Hideo	Split the Attractions (IOI19_split)	C++17	100 / 100	181 ms	21104 KiB

split

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

using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >

const int MAXN = 2e5 + 7;
const int INF = 1e9 + 7;

int tin[MAXN], tim;
int clr[MAXN];
int h[MAXN], sz[MAXN], mn[MAXN];
int x, y, z;

vi g[MAXN], palette;

bool invalid = false;

void precalc (int v, int p = 0){
    tin[v] = ++tim;
    clr[v] = palette[1];
    h[v] = h[p] + 1;
    sz[v] = 1;
    mn[v] = h[v];
    for (int to : g[v]){
        if (!h[to]){
            precalc(to, v);
            sz[v] += sz[to];
            mn[v] = min(mn[v], mn[to]);
        }
        else
            mn[v] = min(mn[v], h[to]);
    }
}

void paint_main (int v, int cclr = 0){
    if (cclr == 0 && clr[v] == palette[1]){
        x--; y++;
    }
    else if (cclr == 1 && clr[v] == palette[0]){
        x++; y--;
    }
    clr[v] = palette[cclr];
    for (int to : g[v])
        if (h[to] - h[v] == 1)
            paint_main(to, cclr);
}

void paint (int v, int point){
    if (y <= 0)
        return;
    if (mn[v] < point)
        paint_main(v, 1);
    else {
        for (int to : g[v])
            if (h[to] - h[v] == 1 && y > 0)
                paint(to, point);
    }
}

void dfs (int v){
    pi mx = {0, 0};
    for (int to : g[v])
        if (h[to] - h[v] == 1 && mx.fr < sz[to])
            mx = {sz[to], to};
    if (x < mx.fr)
        dfs(mx.sc);
    else {
        paint_main(v);
        for (int to : g[v])
            if (h[to] - h[v] == 1 && y > 0)
                paint(to, h[v]);
        if (y > 0)
            invalid = true;
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    if (a >= b && a >= c){
        if (b >= c){
            palette = {2, 3, 1};
            swap(b, c);
        }
        else
            palette = {3, 2, 1};
        swap(a, c);
    }
    else if (b >= a && b >= c){
        if (a >= c)
            palette = {1, 3, 2};
        else {
            palette = {3, 1, 2};
            swap(a, c);
        }
        swap(b, c);
    }
    else {
        if (b >= a){
            palette = {2, 1, 3};
            swap(a, b);
        }
        else
            palette = {1, 2, 3};
    }
    x = a;
    y = b;
    z = c;
    for (int i = 0; i < p.size(); i++){
        g[p[i] + 1].pb(q[i] + 1);
        g[q[i] + 1].pb(p[i] + 1);
    }
    vector < int > res;

    precalc(1);
    y -= n;
    bool stop = false;
    for (int i = 2; i <= n; i++){
        if (sz[i] >= a && sz[1] - sz[i] >= b){
            paint_main(i);
            stop = true;
            break;
        }
        if (sz[i] >= b && sz[1] - sz[i] >= a){
            paint_main(1);
            paint_main(i, 1);
            stop = true;
            break;
        }
    }
    if (stop == false)
        dfs(1);
    if (invalid == true)
        while (res.size() < n)
            res.pb(0);
    else {
        vector < pi > temp;
        for (int i = 1; i <= n; i++)
            temp.pb({tin[i], i});
        sort(all(temp));
        for (int i = n - 1; i >= 0; i--){
            if (clr[temp[i].sc] == palette[0] && x < 0){
                clr[temp[i].sc] = palette[2];
                x++;
            }
            else if (clr[temp[i].sc] == palette[1] && y < 0){
                clr[temp[i].sc] = palette[2];
                y++;
            }
        }
        for (int i = 1; i <= n; i++)
            res.pb(clr[i]);
    }
	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:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < p.size(); i++){
                     ~~^~~~~~~~~~
split.cpp:143:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (res.size() < n)
                ~~~~~~~~~~~^~~

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