oj.uz

Submission #287106

# Submission time Handle Problem Language Result Execution time Memory
287106 2020-08-31T11:51:32 Z dandrozavr Split the Attractions (IOI19_split) C++14
40 / 100
 1854 ms 16628 KB 
/*
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 <= 0.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;
            fill(used, used + n, 0);
            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;
                    }
            if (!byl) continue;
            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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 94 ms 13812 KB ok, correct split
8 Correct 82 ms 10740 KB ok, correct split
9 Correct 101 ms 15604 KB ok, correct split
10 Correct 95 ms 15604 KB ok, correct split
11 Correct 96 ms 13300 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 124 ms 13296 KB ok, correct split
5 Correct 77 ms 9076 KB ok, correct split
6 Correct 98 ms 15604 KB ok, correct split
7 Correct 107 ms 16628 KB ok, correct split
8 Correct 138 ms 11252 KB ok, correct split
9 Correct 80 ms 8948 KB ok, correct split
10 Correct 57 ms 9328 KB ok, correct split
11 Correct 62 ms 9460 KB ok, correct split
12 Correct 60 ms 9328 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 84 ms 9464 KB ok, correct split
3 Correct 30 ms 5496 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 101 ms 12788 KB ok, correct split
6 Correct 102 ms 12280 KB ok, correct split
7 Correct 102 ms 11764 KB ok, correct split
8 Correct 104 ms 12792 KB ok, correct split
9 Correct 99 ms 12916 KB ok, correct split
10 Correct 823 ms 4724 KB ok, no valid answer
11 Correct 833 ms 5620 KB ok, no valid answer
12 Correct 865 ms 8688 KB ok, no valid answer
13 Correct 876 ms 8564 KB ok, no valid answer
14 Correct 857 ms 8816 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 802 ms 2808 KB ok, no valid answer
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 2 ms 2688 KB ok, correct split
8 Correct 2 ms 2688 KB ok, correct split
9 Correct 4 ms 2944 KB ok, correct split
10 Correct 4 ms 2944 KB ok, correct split
11 Correct 2 ms 2688 KB ok, correct split
12 Incorrect 1854 ms 2936 KB jury found a solution, contestant did not
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 94 ms 13812 KB ok, correct split
8 Correct 82 ms 10740 KB ok, correct split
9 Correct 101 ms 15604 KB ok, correct split
10 Correct 95 ms 15604 KB ok, correct split
11 Correct 96 ms 13300 KB ok, correct split
12 Correct 2 ms 2688 KB ok, correct split
13 Correct 2 ms 2688 KB ok, correct split
14 Correct 2 ms 2688 KB ok, correct split
15 Correct 124 ms 13296 KB ok, correct split
16 Correct 77 ms 9076 KB ok, correct split
17 Correct 98 ms 15604 KB ok, correct split
18 Correct 107 ms 16628 KB ok, correct split
19 Correct 138 ms 11252 KB ok, correct split
20 Correct 80 ms 8948 KB ok, correct split
21 Correct 57 ms 9328 KB ok, correct split
22 Correct 62 ms 9460 KB ok, correct split
23 Correct 60 ms 9328 KB ok, correct split
24 Correct 2 ms 2688 KB ok, correct split
25 Correct 84 ms 9464 KB ok, correct split
26 Correct 30 ms 5496 KB ok, correct split
27 Correct 2 ms 2688 KB ok, correct split
28 Correct 101 ms 12788 KB ok, correct split
29 Correct 102 ms 12280 KB ok, correct split
30 Correct 102 ms 11764 KB ok, correct split
31 Correct 104 ms 12792 KB ok, correct split
32 Correct 99 ms 12916 KB ok, correct split
33 Correct 823 ms 4724 KB ok, no valid answer
34 Correct 833 ms 5620 KB ok, no valid answer
35 Correct 865 ms 8688 KB ok, no valid answer
36 Correct 876 ms 8564 KB ok, no valid answer
37 Correct 857 ms 8816 KB ok, no valid answer
38 Correct 2 ms 2688 KB ok, correct split
39 Correct 802 ms 2808 KB ok, no valid answer
40 Correct 2 ms 2688 KB ok, correct split
41 Correct 2 ms 2688 KB ok, correct split
42 Correct 2 ms 2688 KB ok, correct split
43 Correct 2 ms 2688 KB ok, correct split
44 Correct 2 ms 2688 KB ok, correct split
45 Correct 2 ms 2688 KB ok, correct split
46 Correct 4 ms 2944 KB ok, correct split
47 Correct 4 ms 2944 KB ok, correct split
48 Correct 2 ms 2688 KB ok, correct split
49 Incorrect 1854 ms 2936 KB jury found a solution, contestant did not
50 Halted 0 ms 0 KB -