Submission #291508

#	Time	Username	Problem	Language	Result	Execution time	Memory
291508		evpipis	Split the Attractions (IOI19_split)	C++14	100 / 100	189 ms	20724 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];
int vis[len], num[len], low[len], par[len], sz[len];
int n, sz1, sz2, sz3, col1, col2, col3, cnt;

void fix(int u){
    num[u] = low[u] = ++cnt;
    sz[u] = 1;

    for (auto v: adj[u]){
        if (!num[v]){
            par[v] = u;
            fix(v);
            sz[u] += sz[v];
            low[u] = min(low[u], low[v]);
        }
        else if (v != par[u] && num[v] < num[u])
            low[u] = min(low[u], num[v]);
    }
}

void add(int u, vector<int> &mys){
    mys.pb(u);

    for (auto v: adj[u]){
        if (par[v] != u) continue;

        add(v, mys);
    }
}

void dfs(int u, vector<int> &mys){
    for (auto v: adj[u]){
        if (par[v] != u) continue;

        if (sz[v] >= sz1)
            return void(dfs(v, mys));
    }

    mys.pb(u);

    vector<int> temp;
    for (auto v: adj[u]){
        if (par[v] != u) continue;

        if (low[v] >= num[u])
            add(v, mys);
        else
            temp.pb(v);
    }

    while (mys.size() < sz1){
        add(temp.back(), mys);
        temp.pop_back();
    }

    return;
}

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

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

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

void print(vector<int> vec){
    for (auto cur: vec)
        printf("%d ", cur);
    printf("\n");
}

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

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

    fix(1);

    vector<int> fir, sec;
    dfs(1, fir);

    sort(fir.begin(), fir.end());
    for (int i = 1, j = 0; i <= n; i++){
        while (j < fir.size() && fir[j] < i)
            j++;

        if (j < fir.size() && fir[j] == i)
            continue;
        sec.pb(i);
    }

    if (fir.size() >= sec.size())
        swap(fir, sec);

    //printf("fir: "), print(fir);
    //printf("sec: "), print(sec);

    if (fir.size() >= sz1){
        for (auto u: sec)
            vis[u] = col3;
        paint(fir.back(), sz1, col1);
        for (int u: fir)
            if (!vis[u])
                vis[u] = col3;

        for (int u: sec)
            vis[u] = 0;
        paint(sec.back(), sz2, col2);
        for (int u: sec)
            if (!vis[u])
                vis[u] = col3;
    }

	vector<int> out(n, 0);
	for (int i = 1; i <= n; i++)
        out[i-1] = vis[i];
    return out;
}

Compilation message (stderr)

split.cpp: In function 'void dfs(int, std::vector<int>&)':
split.cpp:57:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |     while (mys.size() < sz1){
      |            ~~~~~~~~~~~^~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:92:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   92 |     if (sz3 < sz2)
      |     ^~
split.cpp:95:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   95 |  for (int i = 0; i < P.size(); i++){
      |  ^~~
split.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for (int i = 0; i < P.size(); i++){
      |                  ~~^~~~~~~~~~
split.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         while (j < fir.size() && fir[j] < i)
      |                ~~^~~~~~~~~~~~
split.cpp:112:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         if (j < fir.size() && fir[j] == i)
      |             ~~^~~~~~~~~~~~
split.cpp:123:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |     if (fir.size() >= sz1){
      |         ~~~~~~~~~~~^~~~~~

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