Submission #334571

#	Time	Username	Problem	Language	Result	Execution time	Memory
334571		IgorI	Split the Attractions (IOI19_split)	C++17	100 / 100	192 ms	22272 KiB

split

const long long MOD = 998244353;
const long long INF = 1e9;
const long long INFLL = 1e18;

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef complex<double> cd;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
string Yes[2] = {"No\n", "Yes\n"};
string YES[2] = {"NO\n", "YES\n"};
string Possible[2] = {"Impossible\n", "Possible\n"};
string POSSIBLE[2] = {"IMPOSSIBLE\n", "POSSIBLE\n"};

void dfs2(int v, int p, vi &vis, vvi &g, vi &col, int color, vi &sz, int cent)
{
    vis[v] = 2;
    col[v] = color;
    for (auto u : g[v]) if (vis[u] != 2)
    {
        if ((sz[u] < sz[cent] && sz[u] < sz[cent]) || (sz[v] > sz[cent] && sz[u] > sz[cent]))
            dfs2(u, v, vis, g, col, color, sz, cent);
    }
}

void dfs(int v, int p, vi &vis, vi &sz, int &cent, int &centp, vvi &g, int n)
{
    vis[v] = 1;
    sz[v] = 1;
    for (auto u : g[v]) if (vis[u] == 0)
    {
        dfs(u, v, vis, sz, cent, centp, g, n);
        sz[v] += sz[u];
    }
    if (cent == -1 && sz[v] * 2 >= n)
    {
        cent = v;
        centp = p;
    }
}

void dfs3(int v, int color, vi &vis, vi &col, vi &ans, int A, int &x, vvi &g)
{
    vis[v] = 1;
    if (x) ans[v] = A, x--;
    for (auto u : g[v])
    {
        if (ans[u] == 0 && vis[u] == 0 && (color == -1 || (col[u] == color)))
        {
            dfs3(u, color, vis, col, ans, A, x, g);
        }
    }
}

vi find_split(int n, int a, int b, int c, vi p, vi q)
{
    vvi g(n);
    for (int i = 0; i < p.size(); i++)
    {
        g[p[i]].pb(q[i]);
        g[q[i]].pb(p[i]);
    }
    int cent = -1, centp = -1;
    vi vis(n), sz(n), col(n), croot(n);
    dfs(0, 0, vis, sz, cent, centp, g, n);

    int color = 1;
    vis[cent] = 2;

    for (auto u : g[cent]) if (vis[u] != 2 && sz[u] < sz[cent])
    {
        dfs2(u, cent, vis, g, col, color, sz, cent);
        croot[color] = u;
        color++;
    }
    if (centp != cent)
    {
        dfs2(centp, cent, vis, g, col, color, sz, cent);
        croot[color] = centp;
    }

    //cout << "cent = " << cent << "\n";
    //for (int i = 0; i < n; i++)
    //    cout << col[i] << " ";
    //cout << "\n";

    vector<pii> s = {{a, 1}, {b, 2}, {c, 3}};
    sort(all(s));

    int A = s[0].first;
    vector<int> ans(n);
    vector<int> cnt(n);
    for (int i = 0; i < n; i++)
        cnt[col[i]]++;
    for (int i = 1; i < n; i++)
    {
        if (cnt[i] >= A)
        {
            //cout << i << ", " << croot[i] << "\n";
            int x = s[0].first;
            vis = vi(n, 0);
            dfs3(croot[i], i, vis, col, ans, s[0].second, x, g);
            x = s[1].first;
            vis = vi(n, 0);
            dfs3(cent, -1, vis, col, ans, s[1].second, x, g);
            for (int j = 0; j < n; j++)
                if (ans[j] == 0) ans[j] = s[2].second;
            return ans;
        }
    }
    vector<vector<int> > groups(n);
    for (int i = 0; i < n; i++)
    {
        groups[col[i]].push_back(i);
    }
    for (int j = 0; j < p.size(); j++)
    {
        int f = p[j], t = q[j];
        if (f != cent && t != cent && col[f] != col[t])
        {
            int c1 = col[f];
            int c2 = col[t];
            if (groups[c1].size() < groups[c2].size())
            {
                for (auto v : groups[c1])
                    col[v] = c2, groups[c2].push_back(v);
            }
            else
            {
                for (auto v : groups[c2])
                    col[v] = c1, groups[c1].push_back(v);
            }
            if (groups[c1].size() >= A)
            {
                int i = c1;
                int x = s[0].first;
                vis = vi(n, 0);
                dfs3(croot[i], i, vis, col, ans, s[0].second, x, g);
                x = s[1].first;
                vis = vi(n, 0);
                dfs3(cent, -1, vis, col, ans, s[1].second, x, g);
                for (int j = 0; j < n; j++)
                    if (ans[j] == 0) ans[j] = s[2].second;
                return ans;
            }
            if (groups[c2].size() >= A)
            {
                int i = c2;
                int x = s[0].first;
                vis = vi(n, 0);
                dfs3(croot[i], i, vis, col, ans, s[0].second, x, g);
                x = s[1].first;
                vis = vi(n, 0);
                dfs3(cent, -1, vis, col, ans, s[1].second, x, g);
                for (int j = 0; j < n; j++)
                    if (ans[j] == 0) ans[j] = s[2].second;
                return ans;
            }
        }
    }
    return ans;
}

Compilation message (stderr)

split.cpp: In function 'vi find_split(int, int, int, int, vi, vi)':
split.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < p.size(); i++)
      |                     ~~^~~~~~~~~~
split.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for (int j = 0; j < p.size(); j++)
      |                     ~~^~~~~~~~~~
split.cpp:161:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  161 |             if (groups[c1].size() >= A)
      |                 ~~~~~~~~~~~~~~~~~~^~~~
split.cpp:174:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  174 |             if (groups[c2].size() >= A)
      |                 ~~~~~~~~~~~~~~~~~~^~~~

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