Submission #289877

#	Time	Username	Problem	Language	Result	Execution time	Memory
289877		IgorI	Split the Attractions (IOI19_split)	C++17	22 / 100	852 ms	1048580 KiB

split

#include <bits/stdc++.h>

using namespace std;
 
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int (i) = 0; (i) < (n); (i)++)
 
const int N = 540400;

void dfs(int v, int p, vector<vector<int> > &graph, vector<int> &sz, vector<int> &papa)
{
    papa[v] = p;
    sz[v] = 1;
    for (auto u : graph[v]) if (u != p)
    {
        dfs(u, v, graph, sz, papa);
        sz[v] += sz[u];
    }
}
 
vector<int> find_split(int n, int a, int b, int c, vector<int> v, vector<int> u)
{
    vector<pair<int, int> > z = {{a, 1}, {b, 2}, {c, 3}};
    sort(all(z));
    vector<vector<int> > graph(n);
    for (int i = 0; i < v.size(); i++)
    {
        graph[v[i]].push_back(u[i]);
        graph[u[i]].push_back(v[i]);
    }
    vector<int> sz(n), papa(n);
    dfs(0, 0, graph, sz, papa);
    int t = -1, r = 0;
    for (int i = 0; i < n; i++)
    {
        if (sz[i] >= z[0].first && n - sz[i] >= z[1].first)
        {
            t = i;
            r = 0;
        }
        if (sz[i] >= z[1].first && n - sz[i] >= z[0].first)
        {
            t = i;
            r = 1;
        }
    }
    if (t == -1)
    {
        return vector<int>(n, 0);
    }
    //cout << t << " " << papa[t] << " " << r << endl;
    vector<int> ans(n);
    ans[t] = z[r].second;
    ans[papa[t]] = z[r ^ 1].second;
    vector<int> q0 = {t};
    for (int i = 0; i < q0.size() && q0.size() < z[r].first; i++)
    {
        int v = q0[i];
        for (int j = 0; j < graph[v].size() && q0.size() < z[r].first; j++)
        {
            int u = graph[v][j];
            if (ans[u] == 0)
            {
                ans[u] = z[r].second;
                q0.push_back(u);
            }
        }
    }
    vector<int> q1 = {papa[t]};
    for (int i = 0; i < q1.size() && q1.size() < z[1 ^ r].first; i++)
    {
        int v = q1[i];
        for (int j = 0; j < graph[v].size() && q1.size() < z[1 ^ r].first; j++)
        {
            int u = graph[v][j];
            if (ans[u] == 0)
            {
                ans[u] = z[1 ^ r].second;
                q1.push_back(u);
            }
        }
    }
    //cout << q0.size() << " " << q1.size() << endl;
    for (int i = 0; i < n; i++)
    {
        if (ans[i] == 0)
        {
            ans[i] = z[2].second;
        }
    }
    return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
split.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < q0.size() && q0.size() < z[r].first; i++)
      |                     ~~^~~~~~~~~~~
split.cpp:56:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     for (int i = 0; i < q0.size() && q0.size() < z[r].first; i++)
      |                                      ~~~~~~~~~~^~~~~~~~~~~~
split.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int j = 0; j < graph[v].size() && q0.size() < z[r].first; j++)
      |                         ~~^~~~~~~~~~~~~~~~~
split.cpp:59:58: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         for (int j = 0; j < graph[v].size() && q0.size() < z[r].first; j++)
      |                                                ~~~~~~~~~~^~~~~~~~~~~~
split.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0; i < q1.size() && q1.size() < z[1 ^ r].first; i++)
      |                     ~~^~~~~~~~~~~
split.cpp:70:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |     for (int i = 0; i < q1.size() && q1.size() < z[1 ^ r].first; i++)
      |                                      ~~~~~~~~~~^~~~~~~~~~~~~~~~
split.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int j = 0; j < graph[v].size() && q1.size() < z[1 ^ r].first; j++)
      |                         ~~^~~~~~~~~~~~~~~~~
split.cpp:73:58: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |         for (int j = 0; j < graph[v].size() && q1.size() < z[1 ^ r].first; j++)
      |                                                ~~~~~~~~~~^~~~~~~~~~~~~~~~

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