Submission #1031206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031206		Zicrus	Split the Attractions (IOI19_split)	C++17	11 / 100	59 ms	12372 KiB

split

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

typedef long long ll;

vector<vector<ll>> adj;
vector<bool> vst;
vector<ll> subSize;
vector<ll> parent;
vector<int> res;

ll dfs(ll node, ll par) {
    vst[node] = true;
    parent[node] = par == -1 ? node : par;
    ll sum = 1;
    for (auto &e : adj[node]) {
        if (!vst[e]) {
            sum += dfs(e, node);
        }
    }
    subSize[node] = sum;
    return sum;
}

int subG, subGVal;
void dfs2(ll node) {
    
    if (subGVal-- > 0) {
        res[node] = subG;
    }
    else {
        return;
    }
    vst[node] = true;

    for (auto &e : adj[node]) {
        if (e == parent[node] || vst[e]) continue;
        dfs2(e);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    if (a == 1) {
        int m = p.size();
        vector<int> res(n);
        adj = vector<vector<ll>>(n);
        for (int i = 0; i < m; i++) {
            adj[p[i]].push_back(q[i]);
            adj[q[i]].push_back(p[i]);
        }
        ll lowDeg = 0, deg = n;
        for (int i = 0; i < n; i++) {
            if (adj[i].size() < deg) {
                lowDeg = i;
                deg = adj[i].size();
            }
        }
        queue<ll> qu;
        qu.push(lowDeg);
        while (!qu.empty()) {
            ll node = qu.front(); qu.pop();
            if (c) { res[node] = 3; c--; }
            else if (b) { res[node] = 2; b--; }
            else { res[node] = 1; }
            for (auto &e : adj[node]) {
                if (!res[e]) { qu.push(e); res[e] = 5; }
            }
        }
    
        return res;
    }

    for (int t = 0; t < n; t++) {
        int m = p.size();
        res = vector<int>(n);
        adj = vector<vector<ll>>(n);
        parent = vector<ll>(n);
        subSize = vector<ll>(n);
        for (int i = 0; i < m; i++) {
            adj[p[i]].push_back(q[i]);
            adj[q[i]].push_back(p[i]);
        }
        vst = vector<bool>(n);
        subSize[t] = dfs(t, -1);

        bool possible = 0;
        ll id = 0;
        ll low = min({a, b, c}), high = n - min({a, b, c});
        for (int i = 0; i < n; i++) {
            if (subSize[i] >= low && subSize[i] <= high) { possible = 1; id = i; }
        }

        if (!possible) {
            return res;
        }

        vst = vector<bool>(n);

        vector<pair<ll, ll>> g;
        g.push_back({a, 1});
        g.push_back({b, 2});
        g.push_back({c, 3});
        sort(g.begin(), g.end());

        subG = subSize[id] < n/2 ? g[0].second : g[1].second;
        subGVal = subSize[id] < n/2 ? g[0].first : g[1].first;
        dfs2(id);
        ll pr = parent[id];
        subG = subSize[id] >= n/2 ? g[0].second : g[1].second;
        subGVal = subSize[id] >= n/2 ? g[0].first : g[1].first;
        dfs(id, -1);
        dfs2(pr);

        for (auto &e : res) {
            if (!e) e = g[2].second;
        }

        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:54:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   54 |             if (adj[i].size() < deg) {
      |                 ~~~~~~~~~~~~~~^~~~~
split.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type]
  121 | }
      | ^

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