oj.uz

Submission #287096

# Submission time Handle Problem Language Result Execution time Memory
287096 2020-08-31T11:45:53 Z dandrozavr Split the Attractions (IOI19_split) C++14
18 / 100
 2000 ms 16372 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]);
    }
    if (m == n - 1){
        ld e = TIME;
        while(true)
        {
            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{
        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;
    }
}

#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

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:118:12: warning: unused variable 'e' [-Wunused-variable]
  118 |         ld e = TIME;
      |            ^

Subtask #1
7.0 / 7.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 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 105 ms 15736 KB ok, correct split
8 Correct 84 ms 12920 KB ok, correct split
9 Correct 88 ms 12280 KB ok, correct split
10 Correct 95 ms 16372 KB ok, correct split
11 Correct 110 ms 14068 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 128 ms 12912 KB ok, correct split
5 Correct 75 ms 8568 KB ok, correct split
6 Correct 90 ms 15220 KB ok, correct split
7 Correct 99 ms 14164 KB ok, correct split
8 Correct 126 ms 10744 KB ok, correct split
9 Correct 79 ms 8444 KB ok, correct split
10 Correct 58 ms 8944 KB ok, correct split
11 Correct 60 ms 8944 KB ok, correct split
12 Correct 61 ms 8944 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2720 KB ok, correct split
2 Correct 82 ms 8952 KB ok, correct split
3 Correct 27 ms 5760 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 99 ms 13432 KB ok, correct split
6 Correct 97 ms 13688 KB ok, correct split
7 Correct 102 ms 13560 KB ok, correct split
8 Correct 103 ms 13432 KB ok, correct split
9 Correct 118 ms 12760 KB ok, correct split
10 Execution timed out 2054 ms 4864 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Execution timed out 2078 ms 2688 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.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 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 105 ms 15736 KB ok, correct split
8 Correct 84 ms 12920 KB ok, correct split
9 Correct 88 ms 12280 KB ok, correct split
10 Correct 95 ms 16372 KB ok, correct split
11 Correct 110 ms 14068 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 128 ms 12912 KB ok, correct split
16 Correct 75 ms 8568 KB ok, correct split
17 Correct 90 ms 15220 KB ok, correct split
18 Correct 99 ms 14164 KB ok, correct split
19 Correct 126 ms 10744 KB ok, correct split
20 Correct 79 ms 8444 KB ok, correct split
21 Correct 58 ms 8944 KB ok, correct split
22 Correct 60 ms 8944 KB ok, correct split
23 Correct 61 ms 8944 KB ok, correct split
24 Correct 2 ms 2720 KB ok, correct split
25 Correct 82 ms 8952 KB ok, correct split
26 Correct 27 ms 5760 KB ok, correct split
27 Correct 2 ms 2688 KB ok, correct split
28 Correct 99 ms 13432 KB ok, correct split
29 Correct 97 ms 13688 KB ok, correct split
30 Correct 102 ms 13560 KB ok, correct split
31 Correct 103 ms 13432 KB ok, correct split
32 Correct 118 ms 12760 KB ok, correct split
33 Execution timed out 2054 ms 4864 KB Time limit exceeded
34 Halted 0 ms 0 KB -