oj.uz

Submission #143807

# Submission time Handle Problem Language Result Execution time Memory
143807 2019-08-15T08:28:02 Z dacin21 Split the Attractions (IOI19_split) C++14
18 / 100
 196 ms 17272 KB 
#include "split.h"


#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using fl = long double;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename S, typename T>
void xmin(S&a, T const&b){if(b<a) a=b;}
template<typename S, typename T>
void xmax(S&a, T const&b){if(b>a) a=b;}

template<bool enabled>
struct Debug{
    template<typename S, typename T = void> struct Tag_Printable : false_type {};
    template<typename S> struct Tag_Printable<S, decltype((void)(cerr << declval<S>()))> : true_type {};
    template<typename S, typename T = void> struct Tag_Iterable: false_type {};
    template<typename S> struct Tag_Iterable<S, decltype((void)(begin(declval<S>()), end(declval<S>())))> : true_type {};

    template<typename T, size_t N> struct Tuple_Printer{
        template<typename S>
        static S& print(S& stream, T const&t){
            return Tuple_Printer<T, N-1>::print(stream, t) << ", " << get<N>(t);
        }
    };
    template<typename T> struct Tuple_Printer<T, 0>{
        template<typename S>
        static S& print(S& stream, T const&t){
            return stream << get<0>(t);
        }
    };

    template<typename T, typename... Args>
    Debug& print(T const&x, true_type, Args...){
        #ifdef LOCAL_RUN
        if(enabled){
            cerr << boolalpha << x;
        }
        #endif // LOCAL_RUN
        return *this;
    }
    template<typename T>
    Debug& print(T const&x, false_type, true_type){
        *this << "[";
        bool first = true;
        for(auto &e:x){
            if(!first) *this << ", ";
            *this << e;
            first = false;
        }
        return *this << "]";
    }
    template<typename S, typename T>
    Debug& print(pair<S, T> const&x, false_type, false_type){
        return *this << "(" << x.first << ", " << x.second << ")";
    }
    template<typename... Args>
    Debug& print(tuple<Args...> const&t, false_type, false_type){
        return Tuple_Printer<decltype(t), sizeof...(Args)-1>::print(*this, t);
    }
    template<typename T>
    Debug& operator<<(T const&x){
        return print(x, Tag_Printable<T>{}, Tag_Iterable<T>{});
    }
};
 Debug<true> debug;
// Debug<false> debug; // disable debug printing
#define named(x) string(#x) << " : " <<  x


int n, a, b, c;
vector<bool> vis;
vector<vector<int> > g;

vector<int> L, R, deco;
vector<int> siz;
int tim;


int dfs(int u){
    assert(!vis[u]);
    vis[u] = 1;
    siz[u] = 1;
    L[u] = ++tim;
    deco[L[u]] = u;
    int ret = -1;
    for(auto const&e:g[u]){
        if(!vis[e]){
            const int tmp = dfs(e);
            if(tmp>=0) ret = tmp;
            siz[u]+=siz[e];
        }
    }
    R[u] = tim;
    if(a <= siz[u] && siz[u] <= n-b) ret = u;
    return ret;
}


vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p, vector<int> q) {
    n=n_;
    a=a_;
    b=b_;
    c=c_;
    array<int, 3> label{1,2,3};
    // sort {a,b,c}
    if(c<a) swap(a, c), swap(label[0], label[2]);
    if(c<b) swap(b, c), swap(label[1], label[2]);
    if(b<a) swap(a, b), swap(label[0], label[1]);
    g.assign(n, decltype(g)::value_type{});
    for(int i=0;i<(int)p.size();++i){
        auto const e = p[i], f = q[i];
        g[e].emplace_back(f);
        g[f].emplace_back(e);
    }
    vis.assign(n, false);
    tim=-1;
    L.resize(n);
    R.resize(n);
    siz.resize(n);
    deco.resize(n);

    int tmp = dfs(n/2);
    if(tmp == -1){
        return vector<int>(n, 0);
    }
    // reconstruct
    vector<int> ret(n, label[2]);
    const int X = L[tmp], Y = R[tmp];
    for(int i=0;i<a;++i){
        ret[deco[X+i]] = label[0];
    }
    for(int i=0, j=0;i<b;++j){
        if(j<X || j>Y){
            ret[deco[j]] = label[1];
            ++i;
        }
    }
    assert(count(ret.begin(), ret.end(), label[0]) == a);
    assert(count(ret.begin(), ret.end(), label[1]) == b);
    assert(count(ret.begin(), ret.end(), label[2]) == c);

	return ret;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 252 KB ok, correct split
7 Correct 109 ms 14072 KB ok, correct split
8 Correct 104 ms 17172 KB ok, correct split
9 Correct 106 ms 16480 KB ok, correct split
10 Correct 105 ms 17144 KB ok, correct split
11 Correct 105 ms 17144 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 116 ms 14072 KB ok, correct split
5 Correct 96 ms 9464 KB ok, correct split
6 Correct 157 ms 17272 KB ok, correct split
7 Correct 162 ms 15096 KB ok, correct split
8 Correct 196 ms 11896 KB ok, correct split
9 Correct 125 ms 9464 KB ok, correct split
10 Correct 69 ms 9712 KB ok, correct split
11 Correct 92 ms 9712 KB ok, correct split
12 Correct 76 ms 9728 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 86 ms 9464 KB ok, correct split
3 Correct 35 ms 4088 KB ok, correct split
4 Correct 2 ms 256 KB ok, correct split
5 Correct 130 ms 12664 KB ok, correct split
6 Correct 92 ms 13048 KB ok, correct split
7 Correct 97 ms 11768 KB ok, correct split
8 Incorrect 98 ms 12636 KB jury found a solution, contestant did not
9 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 2 ms 376 KB ok, no valid answer
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 256 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 380 KB ok, correct split
7 Correct 2 ms 376 KB ok, correct split
8 Correct 2 ms 256 KB ok, correct split
9 Correct 4 ms 632 KB ok, correct split
10 Correct 4 ms 632 KB ok, correct split
11 Correct 2 ms 376 KB ok, correct split
12 Correct 4 ms 632 KB ok, correct split
13 Correct 2 ms 376 KB ok, correct split
14 Correct 2 ms 376 KB ok, correct split
15 Correct 2 ms 376 KB ok, correct split
16 Correct 2 ms 376 KB ok, correct split
17 Correct 2 ms 376 KB ok, correct split
18 Correct 2 ms 376 KB ok, correct split
19 Correct 2 ms 376 KB ok, correct split
20 Correct 3 ms 504 KB ok, correct split
21 Correct 4 ms 632 KB ok, correct split
22 Correct 4 ms 632 KB ok, correct split
23 Correct 4 ms 632 KB ok, correct split
24 Incorrect 3 ms 632 KB jury found a solution, contestant did not
25 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 252 KB ok, correct split
7 Correct 109 ms 14072 KB ok, correct split
8 Correct 104 ms 17172 KB ok, correct split
9 Correct 106 ms 16480 KB ok, correct split
10 Correct 105 ms 17144 KB ok, correct split
11 Correct 105 ms 17144 KB ok, correct split
12 Correct 2 ms 256 KB ok, correct split
13 Correct 2 ms 376 KB ok, correct split
14 Correct 2 ms 376 KB ok, correct split
15 Correct 116 ms 14072 KB ok, correct split
16 Correct 96 ms 9464 KB ok, correct split
17 Correct 157 ms 17272 KB ok, correct split
18 Correct 162 ms 15096 KB ok, correct split
19 Correct 196 ms 11896 KB ok, correct split
20 Correct 125 ms 9464 KB ok, correct split
21 Correct 69 ms 9712 KB ok, correct split
22 Correct 92 ms 9712 KB ok, correct split
23 Correct 76 ms 9728 KB ok, correct split
24 Correct 2 ms 376 KB ok, correct split
25 Correct 86 ms 9464 KB ok, correct split
26 Correct 35 ms 4088 KB ok, correct split
27 Correct 2 ms 256 KB ok, correct split
28 Correct 130 ms 12664 KB ok, correct split
29 Correct 92 ms 13048 KB ok, correct split
30 Correct 97 ms 11768 KB ok, correct split
31 Incorrect 98 ms 12636 KB jury found a solution, contestant did not
32 Halted 0 ms 0 KB -