Submission #280376

#	Time	Username	Problem	Language	Result	Execution time	Memory
280376		stoyan_malinin	Split the Attractions (IOI19_split)	C++14	18 / 100	595 ms	1048580 KiB

split

#include "split.h"
//#include "grader.cpp"

#include <set>
#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 5;

int n, m;
vector <int> graph[MAXN];

vector <vector <int>> solve1(int a, int b, int c)
{
    vector <int> order;
    vector <bool> used;

    used.assign(n+5, false);
    function <void(int)> dfs = [&](int x)
    {
        order.push_back(x);
        //cout << x << " ";

        used[x] = true;
        for(int y: graph[x])
        {
            if(used[y]==false) dfs(y);
        }
    };
    //cout << '\n';

    dfs(0);
    vector <vector <int>> out;

    out.push_back({});
    for(int i = 0;i<a;i++) out.back().push_back(order[i]);

    out.push_back({});
    for(int i = a;i<a+b;i++) out.back().push_back(order[i]);

    out.push_back({});
    for(int i = a+b;i<a+b+c;i++) out.back().push_back(order[i]);

    return out;
}

int recogniseSubtask(int a, int b, int c)
{
    int maxDeg = 0;
    for(int x = 0;x<n;x++)
    {
        maxDeg = max(maxDeg, int(graph[x].size()));
    }
    if(maxDeg<=2) return 1;

    if(a==1) return 2;
    if(m==n-1) return 3;
}

int depth[MAXN], treeSize[MAXN];
void DFSInit(int x, int last, int level)
{
    treeSize[x] = 1;
    depth[x] = level;

    for(int y: graph[x])
    {
        if(y==last) continue;
        DFSInit(y, x, level+1);

        treeSize[x] += treeSize[y];
    }
}

int largestKid[MAXN];
multiset <pair <int, int>> ms[MAXN];

int rootPos[MAXN];
void DFSFind(int x, int last, bool &found, int a, int b, int c)
{
    //cout << x << " ---- " << treeSize[x] << '\n';

    if(found==true) return;
    if(graph[x].size()==1)
    {
        largestKid[x] = x;
        ms[x] = {make_pair(1, x)};
    }

    largestKid[x] = -1;
    for(int y: graph[x])
    {
        if(y==last) continue;

        DFSFind(y, x, found, a, b, c);
        if(found==true) return;

        if(largestKid[x]==-1 || ms[ largestKid[y] ].size()>ms[ largestKid[x] ].size())
        {
            largestKid[x] = largestKid[y];
        }
    }

    for(int y: graph[x])
    {
        if(y==last) continue;
        if(largestKid[y]==largestKid[x]) continue;

        for(pair <int, int> item: ms[ largestKid[y] ])
            ms[ largestKid[x] ].insert(item);
    }
    ms[ largestKid[x] ].insert({treeSize[x], x});

    if(treeSize[x]>=a+b)
    {
        auto it = ms[ largestKid[x] ].lower_bound(make_pair(b, -1));
        if(it!=ms[ largestKid[x] ].end() && treeSize[x]-it->first>=a)
        {
            //cout << "found at " << x << '\n';

            found = true;
            rootPos[x] = 1;//a
            rootPos[it->second] = 2;//b
        }
    }
}

vector <vector <int>> solve3(int a, int b, int c)
{
    for(int x = 0;x<n;x++)
    {
        rootPos[x] = 0;
        ms[x].clear();

        depth[x] = 0;
        treeSize[x] = 0;
    }
    DFSInit(0, -1, 1);

    bool found = false;
    DFSFind(0, -1, found, a, b, c);
    if(found==false) return {};

    vector <vector <int>> out;
    function <void(int, int, int, vector <int>&, int)> DFSMark = [&](int x, int last, int col, vector <int> &v, int goal)
    {
        if(v.size()==goal) return;
        //cout << x << " with col: " << col << '\n';

        rootPos[x] = col;
        v.push_back(x);

        for(int y: graph[x])
        {
            if(y==last) continue;
            if(rootPos[y]!=0) continue;

            DFSMark(y, x, col, v, goal);
        }
    };

    for(int x = 0;x<n;x++)
    {
        if(rootPos[x]==1)
        {
            out.push_back({});
            DFSMark(x, -1, rootPos[x], out.back(), a);

            break;
        }
    }
    for(int x = 0;x<n;x++)
    {
        if(rootPos[x]==2)
        {
            out.push_back({});
            DFSMark(x, -1, rootPos[x], out.back(), b);

            break;
        }
    }

    out.push_back({});
    for(int x = 0;x<n;x++)
    {
        if(rootPos[x]==0)
        {
            out.back().push_back(x);
        }
    }

    return out;
}

vector <int> getOutput(vector <vector <int>> v, int a, int b, int c)
{
    if(v.size()==0)
    {
        vector <int> out;
        out.assign(n, 0);

        return out;
    }

    if(v[1].size()==a) swap(v[0], v[1]);
    if(v[2].size()==a) swap(v[0], v[2]);
    if(v[2].size()==b) swap(v[1], v[2]);

    vector <int> out;

    out.resize(a+b+c);
    for(int x: v[0]) out[x] = 1;
    for(int x: v[1]) out[x] = 2;
    for(int x: v[2]) out[x] = 3;

    return out;
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q)
{
    n = _n;
    m = p.size();
    for(int i = 0;i<m;i++)
    {
        graph[ p[i] ].push_back(q[i]);
        graph[ q[i] ].push_back(p[i]);
    }

    int subtask = recogniseSubtask(a, b, c);
    vector <vector <int>> rawOutput;

    if(subtask==1)
    {
        rawOutput = solve1(a, b, c);
        return getOutput(rawOutput, a, b, c);
    }
    if(subtask==2)
    {
        rawOutput = solve1(b, c, a);
        return getOutput(rawOutput, a, b, c);
    }
    if(subtask==3)
    {
        //cout << "subtask 3" << '\n';

        vector <int> sizes = {a, b, c};
        sort(sizes.begin(), sizes.end());

        do
        {
            rawOutput = solve3(a, b, c);
            if(rawOutput.size()!=0) break;
        }
        while(next_permutation(sizes.begin(), sizes.end()));


        return getOutput(rawOutput, a, b, c);

    }
}
/*
5 5
1 2 2
0 1
1 2
2 3
3 4
4 0

5 4
2 2 2
0 1
0 2
0 3
0 4

8 7
2 2 4
0 1
0 2
0 5
0 6
0 7
1 3
2 4
*/

Compilation message (stderr)

split.cpp: In lambda function:
split.cpp:150:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |         if(v.size()==goal) return;
      |            ~~~~~~~~^~~~~~
split.cpp: In function 'std::vector<int> getOutput(std::vector<std::vector<int> >, int, int, int)':
split.cpp:208:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  208 |     if(v[1].size()==a) swap(v[0], v[1]);
      |        ~~~~~~~~~~~^~~
split.cpp:209:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  209 |     if(v[2].size()==a) swap(v[0], v[2]);
      |        ~~~~~~~~~~~^~~
split.cpp:210:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  210 |     if(v[2].size()==b) swap(v[1], v[2]);
      |        ~~~~~~~~~~~^~~
split.cpp: In function 'int recogniseSubtask(int, int, int)':
split.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:233:27: warning: control reaches end of non-void function [-Wreturn-type]
  233 |     vector <vector <int>> rawOutput;
      |                           ^~~~~~~~~

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