답안 #766152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766152	2023-06-25T10:46:14 Z	marvinthang	Simurgh (IOI17_simurgh)	C++17	100 / 100	122 ms	17220 KB

simurgh

/*************************************
*    author: marvinthang             *
*    created: 25.06.2023 11:26:35    *
*************************************/

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

struct DisjointSet {
    
    int n, *lab = nullptr;

    DisjointSet(int _n = 0) {
        resize(_n);
    }

    void reset(void) {
        memset(lab, -1, (n + 1) * sizeof(int));
    }

    void resize(int _n) {
         if (lab != nullptr) delete[] lab;
         n = _n;
         lab = new int[n + 1];
         reset();
    }

    int find(int u) {
        assert(u <= n);
        return lab[u] < 0 ? u : lab[u] = find(lab[u]);
    }

    bool connected(int u, int v) { return find(u) == find(v); }
    bool isRoot(int u) { return lab[u] < 0; }
    int size(int u) { return -lab[find(u)]; }

    bool join(int u, int v) {
        if ((u = find(u)) == (v = find(v))) return false;
        if (lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }

};

using DSU = DisjointSet;

// end of template

const int MAX = 505;

int timeDfs;
vector <int> tree, r_edge, states;
vector <bool> used;
vector <vector <int>> adj;
vector <int> U, V, low, num, par, low_id, pos;

void dfs(int u) {
	num[u] = ++timeDfs;
	for (int id: adj[u]) if (!used[id]) {
		used[id] = true;
		if (u == V[id]) swap(U[id], V[id]);
		int v = V[id];
		if (!num[v]) {
			tree.push_back(id);
			par[v] = id;
			dfs(v);
			if (minimize(low[u], low[v])) low_id[u] = low_id[v];
			if (low[v] > num[u]) states[id] = 1;
		} else {
			assert(num[u] > num[v]);
			r_edge.push_back(id);
			if (minimize(low[u], num[v])) low_id[u] = id;
		}
	}
}

vector <int> trace_path(int u, int p) {
	vector <int> res;
	while (u != p) {
		res.push_back(par[u]);
		u = U[par[u]];
	}
	return res;
}

vector <int> find_roads(int n, vector <int> u, vector <int> v) {
	int m = u.size();
	adj.assign(n, vector<int>());
	tree.clear();
	r_edge.clear();
	U = u; V = v;
	timeDfs = 0;

	num.assign(n, 0);
	low.assign(n, MAX);
	par.assign(n, 0);
	low_id.assign(n, 0);

	pos.assign(m, -1);
	used.assign(m, false);
	states.assign(m, -1);

	REP(i, m) {
		adj[u[i]].push_back(i);
		adj[v[i]].push_back(i);
	}
	dfs(0);

	REP(i, n - 1) pos[tree[i]] = i;
	int cur = count_common_roads(tree);

	for (int e1: tree) if (!~states[e1]) {
		int e2 = low_id[V[e1]];
		vector <int> p = trace_path(U[e2], V[e2]);
		REP(i, p.size()) if (p[i] == e1) {
			swap(p[i], p[0]);
			break;
		}
		bool done = false;
		REP(i, p.size()) {
			int e = p[i];
			tree[pos[e]] = e2;
			int nxt = count_common_roads(tree);
			tree[pos[e]] = e;
			if (nxt != cur) {
				states[e2] = nxt > cur;
				states[e] = nxt < cur;
				REP(j, i) states[p[j]] = states[e2];
				done = true;
				break;
			} else if (~states[e]) {
				states[e2] = states[e];
				REP(j, i + 1) states[p[j]] = states[e];
				done = true;
				break;
			}
		}
		if (!done) for (int e: p) states[e] = 0;
	}
	REP(u, n) {
		vector <int> f;
		for (int id: adj[u]) if (!~states[id]) f.push_back(id);
		while (true) {
			auto ask = [&] (int p) {
				if (!p) return 0;
				vector <int> a(f.begin(), f.begin() + p);
				DSU dsu(n);
				for (int x: a) dsu.join(U[x], V[x]);
				int cnt = 0;
				for (int x: tree) if (dsu.join(U[x], V[x])) {
					cnt += states[x];
					a.push_back(x);
				}
				return count_common_roads(a) - cnt;
			};
			int x = ask(f.size());
			if (!x) break;
			int l = 0, r = (int) f.size() - 1;
			while (l <= r) {
				int m = l + r >> 1;
				if (ask(m + 1) == x) r = m - 1;
				else l = m + 1;
			}
			while (f.size() > l) {
				states[f.back()] = (int) f.size() == l + 1;
				f.pop_back();
			}
		}
	}
	vector <int> res;
	REP(i, m) if (states[i] == 1) res.push_back(i);	
	return res;
}

#ifdef LOCAL
#include "simurgh.h"

#include <cstdio>
#include <cassert>
#include <vector>
#include <cstdlib>
#include <string>

using namespace std;

static int MAXQ = 30000;

static int n, m, q = 0;
static vector<int> u, v;
static vector<bool> goal;

static void wrong_answer() {
	printf("NO\n");
	exit(0);
}

static bool is_valid(const vector<int>& r) {
	if(int(r.size()) != n - 1)
		return false;

	for(int i = 0; i < n - 1; i++)
		if (r[i] < 0 || r[i] >= m)
			return false;

	return true;
}

static int _count_common_roads_internal(const vector<int>& r) {
	if(!is_valid(r))
		wrong_answer();

	int common = 0;
	for(int i = 0; i < n - 1; i++) {
		bool is_common = goal[r[i]];
		if (is_common)
			common++;
	}

	return common;	
}

int count_common_roads(const vector<int>& r) {
	q++;
	if(q > MAXQ)
		wrong_answer();

	return _count_common_roads_internal(r);
}

int main() {
	file("simurgh");
	assert(2 == scanf("%d %d", &n, &m));

	u.resize(m);
	v.resize(m);

	for(int i = 0; i < m; i++)
		assert(2 == scanf("%d %d", &u[i], &v[i]));

	goal.resize(m, false);

	for(int i = 0; i < n - 1; i++) {
		int id;
		assert(1 == scanf("%d", &id));
		goal[id] = true;
	}

	vector<int> res = find_roads(n, u, v);

	if(_count_common_roads_internal(res) != n - 1)
		wrong_answer();
	printf("YES\n");
	printf("q = %d\n", q);

	return 0;
}
#endif

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:199:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  199 |     int m = l + r >> 1;
      |             ~~^~~
simurgh.cpp:203:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  203 |    while (f.size() > l) {
      |           ~~~~~~~~~^~~

Subtask #1

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	1 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	1 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	1 ms	212 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	296 KB	correct

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	1 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	1 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	1 ms	212 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	296 KB	correct
14	Correct	1 ms	340 KB	correct
15	Correct	1 ms	340 KB	correct
16	Correct	1 ms	340 KB	correct
17	Correct	1 ms	340 KB	correct
18	Correct	1 ms	340 KB	correct
19	Correct	1 ms	340 KB	correct
20	Correct	1 ms	340 KB	correct
21	Correct	2 ms	340 KB	correct
22	Correct	1 ms	340 KB	correct
23	Correct	1 ms	300 KB	correct
24	Correct	1 ms	296 KB	correct
25	Correct	1 ms	212 KB	correct
26	Correct	1 ms	340 KB	correct
27	Correct	1 ms	340 KB	correct
28	Correct	1 ms	300 KB	correct
29	Correct	1 ms	212 KB	correct
30	Correct	1 ms	340 KB	correct
31	Correct	1 ms	340 KB	correct
32	Correct	1 ms	340 KB	correct
33	Correct	1 ms	340 KB	correct

Subtask #3

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	1 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	1 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	1 ms	212 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	296 KB	correct
14	Correct	1 ms	340 KB	correct
15	Correct	1 ms	340 KB	correct
16	Correct	1 ms	340 KB	correct
17	Correct	1 ms	340 KB	correct
18	Correct	1 ms	340 KB	correct
19	Correct	1 ms	340 KB	correct
20	Correct	1 ms	340 KB	correct
21	Correct	2 ms	340 KB	correct
22	Correct	1 ms	340 KB	correct
23	Correct	1 ms	300 KB	correct
24	Correct	1 ms	296 KB	correct
25	Correct	1 ms	212 KB	correct
26	Correct	1 ms	340 KB	correct
27	Correct	1 ms	340 KB	correct
28	Correct	1 ms	300 KB	correct
29	Correct	1 ms	212 KB	correct
30	Correct	1 ms	340 KB	correct
31	Correct	1 ms	340 KB	correct
32	Correct	1 ms	340 KB	correct
33	Correct	1 ms	340 KB	correct
34	Correct	21 ms	3924 KB	correct
35	Correct	21 ms	3924 KB	correct
36	Correct	18 ms	3412 KB	correct
37	Correct	6 ms	1236 KB	correct
38	Correct	21 ms	3912 KB	correct
39	Correct	19 ms	3584 KB	correct
40	Correct	19 ms	3284 KB	correct
41	Correct	21 ms	3820 KB	correct
42	Correct	23 ms	3904 KB	correct
43	Correct	8 ms	1876 KB	correct
44	Correct	8 ms	1620 KB	correct
45	Correct	8 ms	1748 KB	correct
46	Correct	7 ms	1588 KB	correct
47	Correct	5 ms	1084 KB	correct
48	Correct	2 ms	468 KB	correct
49	Correct	4 ms	852 KB	correct
50	Correct	5 ms	1236 KB	correct
51	Correct	8 ms	1852 KB	correct
52	Correct	8 ms	1748 KB	correct
53	Correct	7 ms	1620 KB	correct
54	Correct	8 ms	1896 KB	correct
55	Correct	8 ms	1716 KB	correct
56	Correct	8 ms	1620 KB	correct
57	Correct	8 ms	1620 KB	correct

Subtask #4

19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	correct
2	Correct	0 ms	212 KB	correct
3	Correct	61 ms	10968 KB	correct
4	Correct	97 ms	17132 KB	correct
5	Correct	98 ms	17144 KB	correct
6	Correct	93 ms	16788 KB	correct
7	Correct	89 ms	16604 KB	correct
8	Correct	89 ms	16540 KB	correct
9	Correct	97 ms	17004 KB	correct
10	Correct	112 ms	17128 KB	correct
11	Correct	99 ms	17088 KB	correct
12	Correct	99 ms	17220 KB	correct
13	Correct	0 ms	212 KB	correct
14	Correct	97 ms	16768 KB	correct
15	Correct	101 ms	17108 KB	correct

Subtask #5

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	1 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	1 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	1 ms	212 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	296 KB	correct
14	Correct	1 ms	340 KB	correct
15	Correct	1 ms	340 KB	correct
16	Correct	1 ms	340 KB	correct
17	Correct	1 ms	340 KB	correct
18	Correct	1 ms	340 KB	correct
19	Correct	1 ms	340 KB	correct
20	Correct	1 ms	340 KB	correct
21	Correct	2 ms	340 KB	correct
22	Correct	1 ms	340 KB	correct
23	Correct	1 ms	300 KB	correct
24	Correct	1 ms	296 KB	correct
25	Correct	1 ms	212 KB	correct
26	Correct	1 ms	340 KB	correct
27	Correct	1 ms	340 KB	correct
28	Correct	1 ms	300 KB	correct
29	Correct	1 ms	212 KB	correct
30	Correct	1 ms	340 KB	correct
31	Correct	1 ms	340 KB	correct
32	Correct	1 ms	340 KB	correct
33	Correct	1 ms	340 KB	correct
34	Correct	21 ms	3924 KB	correct
35	Correct	21 ms	3924 KB	correct
36	Correct	18 ms	3412 KB	correct
37	Correct	6 ms	1236 KB	correct
38	Correct	21 ms	3912 KB	correct
39	Correct	19 ms	3584 KB	correct
40	Correct	19 ms	3284 KB	correct
41	Correct	21 ms	3820 KB	correct
42	Correct	23 ms	3904 KB	correct
43	Correct	8 ms	1876 KB	correct
44	Correct	8 ms	1620 KB	correct
45	Correct	8 ms	1748 KB	correct
46	Correct	7 ms	1588 KB	correct
47	Correct	5 ms	1084 KB	correct
48	Correct	2 ms	468 KB	correct
49	Correct	4 ms	852 KB	correct
50	Correct	5 ms	1236 KB	correct
51	Correct	8 ms	1852 KB	correct
52	Correct	8 ms	1748 KB	correct
53	Correct	7 ms	1620 KB	correct
54	Correct	8 ms	1896 KB	correct
55	Correct	8 ms	1716 KB	correct
56	Correct	8 ms	1620 KB	correct
57	Correct	8 ms	1620 KB	correct
58	Correct	1 ms	300 KB	correct
59	Correct	0 ms	212 KB	correct
60	Correct	61 ms	10968 KB	correct
61	Correct	97 ms	17132 KB	correct
62	Correct	98 ms	17144 KB	correct
63	Correct	93 ms	16788 KB	correct
64	Correct	89 ms	16604 KB	correct
65	Correct	89 ms	16540 KB	correct
66	Correct	97 ms	17004 KB	correct
67	Correct	112 ms	17128 KB	correct
68	Correct	99 ms	17088 KB	correct
69	Correct	99 ms	17220 KB	correct
70	Correct	0 ms	212 KB	correct
71	Correct	97 ms	16768 KB	correct
72	Correct	101 ms	17108 KB	correct
73	Correct	0 ms	212 KB	correct
74	Correct	102 ms	17076 KB	correct
75	Correct	113 ms	16852 KB	correct
76	Correct	49 ms	8780 KB	correct
77	Correct	98 ms	17124 KB	correct
78	Correct	118 ms	17104 KB	correct
79	Correct	104 ms	17136 KB	correct
80	Correct	122 ms	16928 KB	correct
81	Correct	85 ms	15456 KB	correct
82	Correct	97 ms	16928 KB	correct
83	Correct	72 ms	12944 KB	correct
84	Correct	40 ms	8092 KB	correct
85	Correct	37 ms	7640 KB	correct
86	Correct	30 ms	6148 KB	correct
87	Correct	26 ms	5524 KB	correct
88	Correct	23 ms	4624 KB	correct
89	Correct	23 ms	4768 KB	correct
90	Correct	22 ms	4460 KB	correct
91	Correct	11 ms	2004 KB	correct
92	Correct	6 ms	1108 KB	correct
93	Correct	35 ms	7576 KB	correct
94	Correct	30 ms	6128 KB	correct
95	Correct	36 ms	6124 KB	correct
96	Correct	24 ms	4592 KB	correct
97	Correct	24 ms	4820 KB	correct
98	Correct	26 ms	5252 KB	correct
99	Correct	24 ms	4684 KB	correct
100	Correct	15 ms	2928 KB	correct
101	Correct	9 ms	1324 KB	correct
102	Correct	39 ms	6484 KB	correct
103	Correct	35 ms	6692 KB	correct
104	Correct	34 ms	6480 KB	correct
105	Correct	33 ms	6332 KB	correct