Submission #1021255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021255		vjudge1	Split the Attractions (IOI19_split)	C++17	0 / 100	584 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;

const ll MAXN = 1E5+16;
bool vis[MAXN];
vll adj[MAXN];
ll sz[MAXN];
ll par[MAXN];
vll ord2, ord3;

void dfs_1 (ll u, ll par) {
    ::par[u] = par;
    sz[u] = 1;
    for (ll v : adj[u]) {
        if (v == par) continue;
        dfs_1(v, u);
        sz[u] += sz[v];
    }
}

void dfs_2 (ll u, ll par, ll blk) {
    if (u == blk) return;
    ord2.push_back(u);
    for (ll v : adj[u]) {
        if (v == par) continue;
        dfs_2(v, u, blk);
    }
}

void dfs_3 (ll u, ll par) {
    ord3.push_back(u);
    for (ll v : adj[u]) {
        if (v == par) continue;
        dfs_3(v, u);
    }
}

vi find_split (int n, int aaa, int bbb, int ccc, vi us, vi vs) {
    pair <ll, ll> pa = { aaa, 1 }, pb = { bbb, 2 }, pc = { ccc, 3 };
    if (pa > pb) swap(pa, pb);
    if (pb > pc) swap(pb, pc);
    if (pa > pb) swap(pa, pb);
    ll a = pa.first, b = pb.first, c = pc.first;
    ll m = us.size();
    for (ll i = 0; i < m; i++) {
        adj[us[i]].push_back(vs[i]);
        adj[vs[i]].push_back(us[i]);
    }
    dfs_1(0, 0);
    ll blk = -15;
    for (ll u = 0; u < n; u++) {
        if (sz[u] < a) continue;
        if (n-sz[u] < b) continue;
        blk = u;
    }
    if (blk == -15) return vi(n, 0);
    assert(blk != -15);
    dfs_2(0, 0, blk);
    dfs_3(blk, par[blk]);
    vi ans(n, pc.second);
    if (ord2.size() < b || ord3.size() < a) return vi(n, 0);
    assert(ord2.size() >= b);
    assert(ord3.size() >= a);
    for (ll i = 0; i < a; i++) ans[ord3[i]] = pa.second;
    for (ll i = 0; i < b; i++) ans[ord2[i]] = pb.second;
    return ans;
}

Compilation message (stderr)

split.cpp: In function 'vi find_split(int, int, int, int, vi, vi)':
split.cpp:65:21: 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]
   65 |     if (ord2.size() < b || ord3.size() < a) return vi(n, 0);
      |         ~~~~~~~~~~~~^~~
split.cpp:65:40: 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]
   65 |     if (ord2.size() < b || ord3.size() < a) return vi(n, 0);
      |                            ~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from split.cpp:2:
split.cpp:66:24: 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]
   66 |     assert(ord2.size() >= b);
      |            ~~~~~~~~~~~~^~~~
split.cpp:67:24: 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]
   67 |     assert(ord3.size() >= a);
      |            ~~~~~~~~~~~~^~~~
split.cpp:47:36: warning: unused variable 'c' [-Wunused-variable]
   47 |     ll a = pa.first, b = pb.first, c = pc.first;
      |                                    ^

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