Submission #1064083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064083		jerzyk	Split the Attractions (IOI19_split)	C++17	100 / 100	69 ms	18888 KiB

split

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 100 * 1000 + 7;
bool vis[N]; 
int wys[N], low[N], il[N];
vector<int> answer;

int tab[N];
pair<int, int> cls[3];
bool dcl[3];
vector<int> ed[N];
pair<int, int> bst = make_pair(N * 2, -1);

void DFS(int v)
{
    low[v] = wys[v]; il[v] = 1;
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(il[ed[v][i]])
        {
            low[v] = min(low[v], wys[ed[v][i]]);
            continue;
        }
        wys[ed[v][i]] = wys[v] + 1;
        DFS(ed[v][i]);
        il[v] += il[ed[v][i]];
        low[v] = min(low[v], low[ed[v][i]]);
    }
    //cerr << "dfs: " << v << " " << wys[v] << " " << il[v] << "\n";
    for(int i = 0; i < 2; ++i)
        if(cls[i].st <= il[v])
            bst = min(bst, make_pair(il[v] - cls[i].st, v));
}

void DFST(int v, int clr, int &lft)
{
    if(lft == 0) return;
    vis[v] = true;
    --lft;
    answer[v] = clr;
    //cerr << "dfst: " << v << " " << clr << " " << lft << "\n";
    for(int i = 0; i < (int)ed[v].size(); ++i)
        if(!vis[ed[v][i]] && wys[ed[v][i]] > wys[v])
            DFST(ed[v][i], clr, lft);
}

vector<int> find_split(int n, int Xa, int Xb, int Xc, vector<int> p, vector<int> q)
{
    cls[0] = make_pair(Xa, 1); cls[1] = make_pair(Xb, 2); cls[2] = make_pair(Xc, 3);
    sort(cls, cls + 3);
    //for(int i = 0; i < 3; ++i)
        //cerr << "bst: " << cls[i].st << " " << cls[i].nd << "\n";

    for(int i = 0; i < n; ++i) answer.pb(0);
    for(int i = 0; i < (int)p.size(); ++i)
    {
        ed[p[i]].pb(q[i]);
        ed[q[i]].pb(p[i]);
    }
    DFS(0);
    int xd;
    //cerr << "bst: " << bst.nd << "\n\n";
    if(il[bst.nd] >= cls[1].st && n - il[bst.nd] >= cls[0].st)
    {
        xd = cls[1].st;
        DFST(bst.nd, cls[1].nd, xd);
        xd = cls[0].st;
        DFST(0, cls[0].nd, xd);
        for(int i = 0; i < n; ++i)
            if(answer[i] == 0)
                answer[i] = cls[2].nd;
        return answer;
    }
    if(n - il[bst.nd] >= cls[1].st)
    {
        //cerr << "op2\n\n";
        xd = cls[0].st;
        DFST(bst.nd, cls[0].nd, xd);
        xd = cls[1].st;
        DFST(0, cls[1].nd, xd);
        for(int i = 0; i < n; ++i)
            if(answer[i] == 0)
                answer[i] = cls[2].nd;
        return answer;
    }
    int v = bst.nd;
    int s = n - il[v];
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(wys[ed[v][i]] < wys[v] || low[ed[v][i]] >= wys[v]) continue;
        s += il[ed[v][i]];
    }

    if(s < cls[0].st)
        return answer;

    xd = cls[0].st;
    vis[v] = true;
    DFST(0, cls[0].nd, xd);
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(wys[ed[v][i]] < wys[v] || low[ed[v][i]] >= wys[v]) continue;
        DFST(ed[v][i], cls[0].nd, xd);
    }
    xd = cls[1].st;
    DFST(v, cls[1].nd, xd);
    for(int i = 0; i < n; ++i)
        if(answer[i] == 0)
            answer[i] = cls[2].nd;
    return answer;
}

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