Submission #1256285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256285		nerrrmin	Split the Attractions (IOI19_split)	C++20	18 / 100	57 ms	21964 KiB

split

#include "split.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int m, deg[maxn];
vector < int > g[maxn];
int used[maxn];
int sub[maxn], par[maxn], ver = 0, all;
int in, out;
int c1, c2, c3;
int col1, col2, col3;
void dfs(int beg, int from)
{

    used[beg] = 1;
    sub[beg] = 1;

    for (auto nb: g[beg])
    {
        if(used[nb])continue;
        if(nb == from)continue;
        dfs(nb, beg);
        par[nb] = beg;
        sub[beg] += sub[nb];
    }
    if(sub[beg] >= c1 && all-sub[beg] >= c1)
    {
        if(out < all - sub[beg])
        {ver = beg;
        in = sub[beg];
        out = all-sub[beg];
        }
    }

}


int track[maxn];

int broika;
void rec(int beg, int from, int cvqt)
{
    if(!broika)return;
    broika --;
    track[beg] = cvqt;
    //cout << "gtt " << endl;
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        if(track[nb])continue;
        rec(nb, beg, cvqt);

    }
}
int cnt = 0;
void rec2(int beg, int from, int cvqt)
{
    if(track[beg])return;
    cnt ++;
    if(!broika)return;

    broika --;
    track[beg] = cvqt;
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        if(track[nb])continue;
        rec2(nb, beg, cvqt);
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    m = p.size();
    all = n;
    ver = -1;
    for (int i = 0; i < m; ++ i)
    {
        g[p[i]].pb(q[i]);
        g[q[i]].pb(p[i]);
    }
    if(a <= min(b, c))
    {
        c1 = a;
        col1 = 1;
    }
    else if(b <= min(a, c))
    {
        c1 = b;
        col1 = 2;
    }
    else if(c <= min(a, b))
    {
        c1 = c;
        col1 = 3;
    }

    if(1 != col1 && a >= max(b, c))
    {
        c3 = a;
        col3 = 1;
    }
    else if(2 != col1 && b >= max(a, c))
    {
        c3 = b;
        col3 = 2;
    }
    else if(3 != col1 && c >= max(a, b))
    {
        c3 = c;
        col3 = 3;
    }

    col2 = 6 - col1 - col3;
    c2 = n - c1 - c3;
    assert(c1 + c2 + c3 == n);
    assert(col1 >= 1 && col1 <= 3);
    assert(col2 >= 1 && col2 <= 3);
    assert(col3 >= 1 && col3 <= 3);

    dfs(0, -1);
    vector < int > ans;
    if(ver == -1)
    {
        for (int i = 1; i <= n; ++ i)
            ans.pb(0);
        return ans;
    }


    int pos = ver;
    if(out >= c2)
    {

        broika = c1;
        rec(ver, par[pos], col1);


        broika = c2;

        rec2(par[pos], -1, col2);

        for (int j = 0; j < n; ++ j)
            if(track[j] == 0)track[j] = col3;

        for (int j = 0; j < n; ++ j)
            ans.pb(track[j]);
        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:152:1: warning: control reaches end of non-void function [-Wreturn-type]
  152 | }
      | ^

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