Submission #287099

#	Time	Username	Problem	Language	Result	Execution time	Memory
287099		dandrozavr	Split the Attractions (IOI19_split)	C++14	40 / 100	1871 ms	15608 KiB

split

/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /◐/  /▐/   /▌/ /▀/ /░/ /  / choose your own style!

***IT'S OUR LONG WAY TO THE OIILLLL***


░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/
//#pragma GCC target("avx2")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
namespace fastio {template <class T> ostream &operator<<(ostream &os, const vector<T> &container) {for (auto &u : container)os << u << " ";return os;} template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) {return os << p.first << " " << p.second;}template <class T> ostream &operator<<(ostream &os, set<T> const& con) {    for (auto &u : con)        os << u << " ";return os;} void pr() {} template <typename T, typename... args> void pr(T x, args... tail) {cout << x << " ";pr(tail...);}} using namespace fastio;
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define _ <<" "<<
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
#define uint unsigned int
//#define int long long
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
const int rx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
const int ry[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int kx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int ky[8] = {2, -2, 2, -2, 1, -1, 1, -1};
//const ld pi = acos(-1.0);
const int N = 1e5 + 5;
const int M = 1e9 + 7;

int used[N], ost;
vector < int > g[N];

void fine(int v, int col, int pr = -1){
    used[v] = col;
//    cout << v _ col << endl;
    --ost;
    if (!ost) return;
    for (int to : g[v])
    if (to != pr && !used[to]){
        fine(to, col, v);
        if (!ost) return;
    }
}
int sz[N], Pr, pos;
void dfs(int v, int need, int pr = -1){
    sz[v] = 1;
    bool bad = 0;
    for (int to : g[v])
    if (to != pr){
        dfs(to, need, v);
        if (pos != -1) return;
        if (sz[to] >= need)
            bad = 1;
        sz[v] += sz[to];
    }
    if (!bad && sz[v] >= need){
        pos = v;
        Pr = pr;
    }
//    cout << v _ sz[v] _ need _ bad _ pos << endl;
}

vector < int > vis;
int Sz(int v, int pr = -1){
    if (pr == -1) vis = {};
    vis.pb(v);
    used[v] = 4;
    int ans = 1;
    for (int to : g[v])
        if (to != pr && !used[to])
            ans += Sz(to, v);
//    cout << v _ ans << endl;
    return ans;
}

vector < int > find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
    int m = p.size();
    int oa = 1, ob = 2, oc = 3;
    if (a > b) swap(a, b), swap(oa, ob);
    if (b > c) swap(b, c), swap(ob, oc);
    if (a > b) swap(a, b), swap(oa, ob);
    for (int i = 0; i < m; ++i){
        g[p[i]].pb(q[i]);
        g[q[i]].pb(p[i]);
    }
    ld e = TIME;
    vector < int > emp;
    for (int i = 0; i < n; ++i)emp.pb(0);
    if (m == n - 1){
        while(TIME - e <= 1.8)
        {
            int ver = gen() % n;
            pos = -1;
            dfs(ver, a);
            if (pos == -1 || n - sz[pos] < a) continue;
            if (sz[pos] <= n - sz[pos]){
                ost = a; fine(pos, oa, Pr);
                ost = b; fine(Pr, ob, pos);
            } else {
                ost = a; fine(Pr, oa, pos);
                ost = b; fine(pos, ob, Pr);
            }
            vector < int > ans;
            for (int i = 0; i < n; ++i)
                if (used[i]) ans.pb(used[i]); else ans.pb(oc);
            return ans;
        }
    } else{
        while(TIME - e <= 1.85){
            vector < int > ans;
            ost = b;
            fine(gen() % n, ob);
            bool byl = 0;
            for (int i = 0; i < n && !byl; ++i)
            if (used[i] == ob && !byl)
                for (int to : g[i])
                    if (!used[to] && Sz(to) >= a){
                        ost = a;
                        for (int i = 0; i < a; ++i)
                            used[vis[i]] = oa;
                        byl = 1;
                        break;
                    }
            for (int i = 0; i < n; ++i){
                if (used[i] < 4 && used[i]) ans.pb(used[i]); else ans.pb(oc);
            }
            return ans;
        }
    }
    return emp;
}

#ifdef Estb_probitie
main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
	int n, m, a, b, c;
	assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
	vector<int> p(m), q(m);
	for (int i=0; i<m; i++)
		assert(2 == scanf("%d%d", &p[i], &q[i]));
	fclose(stdin);
	vector<int> result = find_split(n, a, b, c, p, q);

	for (int i=0; i<(int)result.size(); i++)
		printf("%s%d", ((i>0)?" ":""), result[i]);
	printf("\n");
	return 0;
}
    #endif // Estb_probitie

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