Submission #1064949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064949		ewirlan	Split the Attractions (IOI19_split)	C++17	18 / 100	79 ms	38276 KiB

split

//
#ifndef __SIZEOF_INT128__
    #define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
    string name{""};
    time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
    duration<float, std::milli> dur;
    Timer() = default;
    Timer(string nm): name(nm) {}
    ~Timer() {
        end = high_resolution_clock::now(); dur= end - start;
        cout << "@" << name << "> " << dur.count() << " ms" << '\n';
    }
};
template <typename T = int> inline T in()
{
    static T x;
    std::cin >> x;
    return x;
}
std::string yn(bool b)
{
    if(b) return "YES\n";
    else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
    for(const auto& i : wek)out << i << ' ';
    return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
    out << '{'<<par.first<<", "<<par.second<<"}";
    return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
constexpr int maxn = 1e5 + 3;
vector <int> graf[maxn];
int low[maxn], siz[maxn], pok[maxn];
vector <int> u[maxn], sy[maxn];
int dfs(int w, int l, int r, int p = 1)
{
    low[w] = pok[w] = p;
    siz[w] = 1;
    int s(1);
    vector <pair <int, int>> v;
    for(auto i: graf[w]){
        if(!pok[i]){
            sy[w].pb(i);
            int d(dfs(i, l, r, p+1));
            if(d)return d;
            low[w] = min(low[w], low[i]);
            siz[w] += siz[i];
            if(low[i] >= p){
                s += siz[i];
                u[w].pb(i);
            }
            else if(siz[i] < l)v.pb(i, siz[i]);
        }
        else if(pok[i] != pok[w]-1)low[w] = min(low[w], pok[i]);
    }
    // cerr << w << ": " << v << '\n';
    int i(0);
    while(s < l && i < sz(v)){
        u[w].pb(v[i].first);
        s += v[i++].second;
    }
    if(l <= s && s <= r)return w+1;
    return 0;
}
bool wpo[maxn];
void dfs2(int w){
    wpo[w] = 1;
    for(auto i: sy[w])dfs2(i);
}
vector <int> odp;
int dfs3(int w, bool b, int f, int k)
{
    // cerr << '(' << w << ' ' << b << ' ' << f << ' ' << k << ")\n";
    odp[w] = f;
    --k;
    for(auto i: graf[w])if(k && !odp[i] && wpo[i] == b)k = dfs3(i, b, f, k);
    return k;
}
vector <int> find_split(const int n, int aa, int bb, int cc, vector <int> p, vector <int> q)
{
    const int m(sz(p));
    int a(min({aa, bb, cc})), c(max({aa, bb, cc})), b(n-a-c);
    int ia(aa < bb ? (aa < cc ? 1 : 3) : (bb < cc ? 2 : 3)), ic(aa < bb ? (bb < cc ? 3 : 2) : (aa < cc ? 3 : 1)), ib(6 - ia - ic);
    rep(i, 0, m){
        graf[p[i]].pb(q[i]);
        graf[q[i]].pb(p[i]);
    }
    int d(dfs(0, a, n-b));
    if(d == 0){
        rep(i, 0, n){
            low[i] = pok[i] = siz[i] = 0;
            u[i].clear();
            sy[i].clear();
        }
        d = dfs(0, b, n-a);
        if(d == 0)return vector <int>(n, 0);
    }
    --d;
    odp = vector <int>(n, 0);
    wpo[d] = 1;
    for(auto i: u[d])dfs2(i);
    // cerr << d << '\n';
    // rep(i, 0, n)cerr << i << ": " << siz[i] << ' ' << pok[i] << ' ' << low[i] << " {" << sy[i] << "} {" << u[i] << "} " << wpo[i] << '\n';
    int e(-1);
    rep(i, 0, n)if(!wpo[i]){
        e = i;
        break;
    }
    dfs3(d, 1, ia, a);
    dfs3(e, 0, ib, b);
    rep(i, 0, n)if(!odp[i])odp[i] = ic;
    return odp;
}

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