Submission #290055

#	Time	Username	Problem	Language	Result	Execution time	Memory
290055		evpipis	Split the Attractions (IOI19_split)	C++14	40 / 100	145 ms	17852 KiB

split

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

#define pb push_back
const int len = 1e5+5;
vector<int> adj[len], out;
int vis[len], n, sz1, sz2, sz3, col1, col2, col3;

void paint(int u, int p, int &rem, int col){
    //printf("painting: u = %d, p = %d, rem = %d, col = %d\n", u, p, rem, col);
    vis[u] = col, rem--;
    if (rem == 0) return;

    for (auto v: adj[u]){
        if (v == p || vis[v]) continue;

        paint(v, u, rem, col);
        if (rem == 0) return;
    }
}

struct{
    int sz[len];

    int fix(int u, int p, int &yes){
        //printf("fix: u = %d, p = %d\n", u, p);
        int ans = 1;
        for (auto v: adj[u]){
            if (v == p) continue;

            int sz = fix(v, u, yes);
            if (yes) return 0;
            ans += sz;

            if (sz1 <= sz && sz2 <= n-sz){
                paint(v, u, sz1, col1);
                paint(u, v, sz2, col2);
                return (yes = 1);
            }
            if (sz1 <= n-sz && sz2 <= sz){
                paint(u, v, sz1, col1);
                paint(v, u, sz2, col2);
                return (yes = 1);
            }
        }

        return ans;
    }

    void solve(){
        int yes = 0;
        fix(1, 1, yes);

        if (!yes) return;

        for (int i = 1; i <= n; i++){
            if (!vis[i]) vis[i] = col3;

            out[i-1] = vis[i];
        }
    }
} sub3;

struct{
    void solve(){
        int st = 1;
        for (int i = 1; i <= n; i++)
            if (adj[i].size() == 1)
                st = i;
        paint(st, st, sz2, col2);

        for (int i = 1; i <= n; i++)
            if (!vis[i]){
                paint(i, i, sz1, col1);
                break;
            }

        for (int i = 1; i <= n; i++){
            if (!vis[i])
                vis[i] = col3;

            out[i-1] = vis[i];
        }
    }
} sub12;

vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
    n = N;
    sz1 = A, sz2 = B, sz3 = C;
    col1 = 1, col2 = 2, col3 = 3;
    if (sz2 < sz1)
        swap(sz2, sz1), swap(col2, col1);
    if (sz3 < sz1)
        swap(sz3, sz1), swap(col3, col1);
    if (sz3 < sz2)
        swap(sz3, sz2), swap(col3, col2);

    //printf("sz1 = %d, sz2 = %d, sz3 = %d\n", sz1, sz2, sz3);
    //printf("col1 = %d, col2 = %d, col3 = %d\n", col1, col2, col3);

	for (int i = 0; i < P.size(); i++){
        int a = P[i], b = Q[i];
        a++, b++;
        adj[a].pb(b);
        adj[b].pb(a);
	}

	out.resize(n, 0);
	if (P.size() == n-1)
        sub3.solve();
    else
        sub12.solve();

    return out;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for (int i = 0; i < P.size(); i++){
      |                  ~~^~~~~~~~~~
split.cpp:110:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |  if (P.size() == n-1)
      |      ~~~~~~~~~^~~~~~

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