Submission #1077695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077695		Ignut	Split the Attractions (IOI19_split)	C++17	11 / 100	60 ms	13480 KiB

split

// Ignut

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 123;
int n;
int a, b, c;
int colorA = 1, colorB = 2, colorC = 3;

vector<int> g[MAXN];

int vert = -1;

vector<int> res;

int lim;

void dfs(int v, int col) {
    if (lim == 0) return;
    res[v] = col;
    lim --;
    if (lim == 0) return;
    for (int to : g[v]) {
        if (res[to] != 3)
            continue;
        if (lim == 0) return;
        dfs(to, col);
        if (lim == 0) return;
    }
    if (lim == 0) return;
}

vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
    int M = P.size();
    for (int i = 0; i < M; i ++) {
        g[P[i]].push_back(Q[i]);
        g[Q[i]].push_back(P[i]);
    }

    res.assign(N, 3);
    
    vector<pair<int, int>> vec;
    for (int i = 0; i < N; i ++) vec.push_back({g[i].size(), i});
    sort(vec.begin(), vec.end());
    vert = vec[0].second;

    res[vert] = 1;

    int start = 0;
    if (start == vert) start ++;

    lim = B;
    dfs(start, 2);

    if (lim != 0) N /= 0;

    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:57:21: warning: division by zero [-Wdiv-by-zero]
   57 |     if (lim != 0) N /= 0;
      |                   ~~^~~~

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