oj.uz

답안 #287099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287099 2020-08-31T11:49:40 Z dandrozavr Split the Attractions (IOI19_split) C++14
40 / 100
 1871 ms 15608 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 <= 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.0 / 7.0

# 결과 실행 시간 메모리 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 96 ms 12532 KB ok, correct split
8 Correct 78 ms 11252 KB ok, correct split
9 Correct 100 ms 15092 KB ok, correct split
10 Correct 98 ms 15604 KB ok, correct split
11 Correct 94 ms 13300 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 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 123 ms 13296 KB ok, correct split
5 Correct 75 ms 9076 KB ok, correct split
6 Correct 94 ms 15608 KB ok, correct split
7 Correct 84 ms 11636 KB ok, correct split
8 Correct 124 ms 11252 KB ok, correct split
9 Correct 86 ms 8948 KB ok, correct split
10 Correct 62 ms 9328 KB ok, correct split
11 Correct 58 ms 9328 KB ok, correct split
12 Correct 62 ms 9328 KB ok, correct split

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 83 ms 9460 KB ok, correct split
3 Correct 27 ms 5376 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 93 ms 11764 KB ok, correct split
6 Correct 99 ms 12784 KB ok, correct split
7 Correct 102 ms 12660 KB ok, correct split
8 Correct 98 ms 12020 KB ok, correct split
9 Correct 100 ms 11764 KB ok, correct split
10 Correct 1823 ms 4852 KB ok, no valid answer
11 Correct 1836 ms 6260 KB ok, no valid answer
12 Correct 1864 ms 9912 KB ok, no valid answer
13 Correct 1871 ms 9716 KB ok, no valid answer
14 Correct 1867 ms 9968 KB ok, no valid answer

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2688 KB ok, correct split
2 Correct 1803 ms 2720 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 5 ms 2944 KB ok, correct split
10 Correct 5 ms 2944 KB ok, correct split
11 Correct 2 ms 2688 KB ok, correct split
12 Incorrect 6 ms 2944 KB invalid split: #1=0, #2=1601, #3=800
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 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 96 ms 12532 KB ok, correct split
8 Correct 78 ms 11252 KB ok, correct split
9 Correct 100 ms 15092 KB ok, correct split
10 Correct 98 ms 15604 KB ok, correct split
11 Correct 94 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 123 ms 13296 KB ok, correct split
16 Correct 75 ms 9076 KB ok, correct split
17 Correct 94 ms 15608 KB ok, correct split
18 Correct 84 ms 11636 KB ok, correct split
19 Correct 124 ms 11252 KB ok, correct split
20 Correct 86 ms 8948 KB ok, correct split
21 Correct 62 ms 9328 KB ok, correct split
22 Correct 58 ms 9328 KB ok, correct split
23 Correct 62 ms 9328 KB ok, correct split
24 Correct 2 ms 2688 KB ok, correct split
25 Correct 83 ms 9460 KB ok, correct split
26 Correct 27 ms 5376 KB ok, correct split
27 Correct 2 ms 2688 KB ok, correct split
28 Correct 93 ms 11764 KB ok, correct split
29 Correct 99 ms 12784 KB ok, correct split
30 Correct 102 ms 12660 KB ok, correct split
31 Correct 98 ms 12020 KB ok, correct split
32 Correct 100 ms 11764 KB ok, correct split
33 Correct 1823 ms 4852 KB ok, no valid answer
34 Correct 1836 ms 6260 KB ok, no valid answer
35 Correct 1864 ms 9912 KB ok, no valid answer
36 Correct 1871 ms 9716 KB ok, no valid answer
37 Correct 1867 ms 9968 KB ok, no valid answer
38 Correct 3 ms 2688 KB ok, correct split
39 Correct 1803 ms 2720 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 5 ms 2944 KB ok, correct split
47 Correct 5 ms 2944 KB ok, correct split
48 Correct 2 ms 2688 KB ok, correct split
49 Incorrect 6 ms 2944 KB invalid split: #1=0, #2=1601, #3=800
50 Halted 0 ms 0 KB -