Submission #287068

#	Time	Username	Problem	Language	Result	Execution time	Memory
287068		dandrozavr	Split the Attractions (IOI19_split)	C++14	0 / 100	116 ms	16420 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;
    }
}

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();
    if (a > b) swap(a, b);
    if (b > c) swap(b, c);
    if (a > b) swap(a, b);
    for (int i = 0; i < m; ++i){
        g[p[i]].pb(q[i]);
        g[q[i]].pb(p[i]);
    }
//    if (m == n - 1){
//
//    } else
        {
        vector < int > ans;
        ost = b;
        fine(0, 2);
        bool byl = 0;
        for (int i = 0; i < n && !byl; ++i)
        if (used[i] == 2 && !byl)
            for (int to : g[i])
                if (!used[to] && sz(to) >= a){
                    ost = a;
                    for (int i = 0; i < a; ++i)
                        used[vis[i]] = 1;
                    byl = 1;
                    break;
                }
        for (int i = 0; i < n; ++i){
            if (used[i] >= 1 && used[i] <= 2) ans.pb(used[i]); else ans.pb(3);
        }
        return ans;
    }
}

#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: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36