Submission #278418

#	Time	Username	Problem	Language	Result	Execution time	Memory
278418		Kastanda	Split the Attractions (IOI19_split)	C++14	100 / 100	214 ms	26220 KiB

split

// M
#include<bits/stdc++.h>
#include "split.h"
using namespace std;
const int N = 100005;
int n, K[3], Cl[3], M[N], SZ[N], MR[N];
vector < int > C, vec, Adj[N], Ad[N], G[N];
void DFS(int v)
{
        M[v] = SZ[v] = 1;
        for (int u : Adj[v])
                if (!M[u])
                {
                        Ad[v].push_back(u);
                        Ad[u].push_back(v);
                        DFS(u);
                        SZ[v] += SZ[u];
                }
}
int Centroid(int v, int p = -1)
{
        for (int u : Ad[v])
                if (u != p && SZ[u] * 2 > n)
                        return Centroid(u, v);
        return v;
}
void DFS2(int v, int p = -1)
{
        SZ[v] = 1;
        for (int u : Ad[v])
                if (u != p)
                        DFS2(u, v), SZ[v] += SZ[u];
}
void Color(int v, int p, int c)
{
        if (!K[c])
                return ;
        C[v] = Cl[c];
        K[c] --;
        for (int u : Ad[v])
                if (u != p && !C[u])
                        Color(u, v, c);
}
void MarkAs(int v, int p, int mr)
{
        MR[v] = mr;
        for (int u : Ad[v])
                if (u != p)
                        MarkAs(u, v, mr);
}
void Go(int v)
{
        M[v] = 1;
        vec.push_back(v);
        for (int u : G[v])
                if (!M[u]) Go(u);
}
vector < int > find_split(int _n, int a, int b, int c, vector < int > V, vector < int > U)
{
        n = _n;
        K[0] = a; K[1] = b; K[2] = c;
        Cl[0] = 1; Cl[1] = 2; Cl[2] = 3;
        for (int i = 0; i < 3; i ++)
                for (int j = i + 1; j < 3; j ++)
                        if (K[i] > K[j])
                                swap(K[i], K[j]), swap(Cl[i], Cl[j]);
        assert(K[0] <= K[1] && K[1] <= K[2]);
        int m = (int)V.size();
        for (int i = 0; i < m; i ++)
        {
                Adj[V[i]].push_back(U[i]);
                Adj[U[i]].push_back(V[i]);
        }
        DFS(0);
        int Cent = Centroid(0);
        DFS2(Cent);

        C = vector < int > (n, 0);
        for (int u : Ad[Cent])
                if (SZ[u] >= K[0])
                {
                        Color(u, Cent, 0);
                        Color(Cent, -1, 1);
                        for (int i = 0; i < n; i ++)
                                if (!C[i])
                                        C[i] = Cl[2];
                        return C;
                }

        for (int u : Ad[Cent])
                MarkAs(u, Cent, u);

        for (int i = 0; i < m; i ++)
                if (V[i] != Cent && U[i] != Cent && MR[V[i]] != MR[U[i]])
                        G[MR[V[i]]].push_back(MR[U[i]]),
                        G[MR[U[i]]].push_back(MR[V[i]]);
        memset(M, 0, sizeof(M));
        for (int u : Ad[Cent])
                if (!M[u])
                {
                        vec.clear();
                        Go(u);
                        int sz = 0;
                        for (int i = 0; i < (int)vec.size(); i ++)
                        {
                                sz += SZ[vec[i]];
                                if (sz >= K[0])
                                {
                                        for (int j = 0; j <= i; j ++)
                                                Color(vec[j], Cent, 0);
                                        Color(Cent, -1, 1);
                                        for (int i = 0; i < n; i ++)
                                                if (!C[i])
                                                        C[i] = Cl[2];
                                        return C;
                                }
                        }
                }
        return C;
}

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