Submission #889566

#	Time	Username	Problem	Language	Result	Execution time	Memory
889566		vjudge1	Split the Attractions (IOI19_split)	C++17	18 / 100	70 ms	24052 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    vi re(n, 0);
    vector<vi> L(n);
    for(int i = 0; i < p.size(); ++i) {
        L[p[i]].push_back(q[i]);
        L[q[i]].push_back(p[i]);
    }

    if(a == 1) {
        vi viz(n, 0);
        int nrb = 0;
        function<void(int)> dfs = [&](int u) {
            viz[u] = 1;
            if(nrb < b) {
                re[u] = 2;
                ++nrb;
            }
            for(auto it : L[u]) {
                if(!viz[it])
                    dfs(it);
            }   
        };
        dfs(0);
        for(auto &it : re) {
            if(!it && a) {
                it = 1;
                --a;
            }
            if(!it) it = 3;
        }
        return re;
    }
    if(p.size() == n && !L[0].empty()) {
        int v = L[0].back();
        L[0].pop_back();
        sort(L[v].rbegin(), L[v].rend());
        L[v].pop_back();
        p.pop_back();
    }
    if(p.size() == n - 1) {
        vector<pair<int, int> > Vcul = {{a, 1}, {b, 2}, {c,3}};
        sort(Vcul.begin(), Vcul.end());
        int a = Vcul[0].first;
        vi sz(n, 0), dpa(n, -1), fiu(n, -1);
        function<void(int, int)> dfs = [&](int u, int p) {
            sz[u] = 1;
            dpa[u] = -1;
            for(auto it : L[u]) {
                if(it != p) {
                    dfs(it, u);
                    sz[u] += sz[it];
                }
            }
            if(sz[u] >= a) {
                dpa[u] = 0;
            }
            for(auto it : L[u]) {
                if(dpa[it] != -1) {
                    if(dpa[u] < dpa[it] + sz[u] - sz[it]) {
                        dpa[u] = dpa[it] + sz[u] - sz[it];
                        fiu[u] = it;
                    }
                }
            }
        };
        dfs(0, -1);
        int nra = 0, nrb = 0;
        function<void(int, int, int)> dfs2 = [&](int u, int p, int tip) {
            if(tip == 0 && fiu[u] == -1) {
                tip = 2; /// fake news, eu sunt dfa
            } 
            if(tip == 0) { ///dau dpa mai jos, incerc sa fiu cul1
                if(nrb < Vcul[1].first) {
                    ++nrb;
                    re[u] = Vcul[1].second;
                } else re[u] = Vcul[2].second;
                dfs2(fiu[u], u, 0);
                for(auto it : L[u])
                    if(it != p && it != fiu[u])
                        dfs2(it, u, 1);
            }
            if(tip == 1) {
                if(nrb < Vcul[1].first) {
                    ++nrb;
                    re[u] = Vcul[1].second;
                } else re[u] = Vcul[2].second;
                for(auto it : L[u])
                    if(it != p)
                        dfs2(it, u, 1);
            }
            if(tip == 2) {
                if(nra < Vcul[0].first) {
                    ++nra;
                    re[u] = Vcul[0].second;
                } else re[u] = Vcul[2].second;
                for(auto it : L[u])
                    if(it != p)
                        dfs2(it, u, 2);
            }
        };
        dfs2(0, -1, 0);
        if(nra < Vcul[0].first || nrb < Vcul[1].first)
            return vi(n, 0);
        return re;
    }
    assert(0);
    return re;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:11:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0; i < p.size(); ++i) {
      |                    ~~^~~~~~~~~~
split.cpp:40:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if(p.size() == n && !L[0].empty()) {
      |        ~~~~~~~~~^~~~
split.cpp:47:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     if(p.size() == n - 1) {
      |        ~~~~~~~~~^~~~~~~~

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