Submission #280338

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

split

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

#include <iostream>
#include <functional>

using namespace std;

const int MAXN = 1e5 + 5;

int n;
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;
}

vector <int> getOutput(vector <vector <int>> v, int a, int b, int c)
{
    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;
    for(int i = 0;i<p.size();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);
    }
}
/*
5 5
1 2 2
0 1
1 2
2 3
3 4
4 0
*/

Compilation message (stderr)

split.cpp: In function 'std::vector<int> getOutput(std::vector<std::vector<int> >, int, int, int)':
split.cpp:62:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |     if(v[1].size()==a) swap(v[0], v[1]);
      |        ~~~~~~~~~~~^~~
split.cpp:63:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |     if(v[2].size()==a) swap(v[0], v[2]);
      |        ~~~~~~~~~~~^~~
split.cpp:64:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     if(v[2].size()==b) swap(v[1], v[2]);
      |        ~~~~~~~~~~~^~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0;i<p.size();i++)
      |                   ~^~~~~~~~~
split.cpp: In function 'int recogniseSubtask(int, int, int)':
split.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
   58 | }
      | ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:86:27: warning: control reaches end of non-void function [-Wreturn-type]
   86 |     vector <vector <int>> rawOutput;
      |                           ^~~~~~~~~

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