oj.uz

Submission #58822

# Submission time Handle Problem Language Result Execution time Memory
58822 2018-07-19T14:58:39 Z reality Simurgh (IOI17_simurgh) C++17
100 / 100
 1379 ms 30164 KB 
#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1024;
int w[N][N];
int s[N][N];
int f[N];
vi g[N];
int p[N];
int get(int k) {
	return k == p[k] ? k : p[k] = get(p[k]);
} 
int was[N * N];
vi E;
vi find_roads(int n,vi u,vi v) {
	if (n == 2) {
		return vi{0};
	}
	int m = u.size();
	memset(w,-1,sizeof(w));
	memset(s,-1,sizeof(s));
	for (int i = 0;i < m;++i)
		w[u[i]][v[i]] = w[v[i]][u[i]] = i;
	vi answer;	
	vi ee;
	for (int l = 0;l < n;++l)
		p[l] = l;
	for (int i = 0;i < m;++i)
		if (get(u[i]) != get(v[i])) {
			g[u[i]].pb(v[i]);
			g[v[i]].pb(u[i]);
			ee.pb(i);
			was[i] = 1;
			p[get(u[i])] = get(v[i]);
		}
	for (int i = 0;i < m;++i) 
		if (!was[i]) {
			queue < int > Q;
			Q.push(u[i]);
			for (int j = 0;j < n;++j)
				f[j] = -1;
			f[u[i]] = u[i];
			while (!Q.empty() && f[v[i]] == -1) {
				int node = Q.front();
				Q.pop();
				for (auto it : g[node])
					if (f[it] == -1)
						f[it] = node,Q.push(it);
			}
			vi E;
			for (int j = v[i];j != u[i];j = f[j])
				E.pb(w[j][f[j]]);
			int ok = 0;
			vi ed;
			for (auto it : ee)
				ed.pb(it);
			ed.pb(i);
			for (auto it : E)
				ok |= was[it] == 1;
			if (ok) {
				E.pb(i);
				int index = -1;
				for (int i = 0;i < E.size();++i)
					if (was[E[i]] == 3)
						index = E[i];
				int ind = -1;
				for (int i = 0;i < E.size();++i)
					if (was[E[i]] == 2)
						ind = E[i];
				vector < pii > rs;
				if (index != -1) {
					vi e;
					for (auto it : ed)
						if (it != index)
							e.pb(it);
					rs.pb(mp(count_common_roads(e),index));
				}
				if (ind != -1) {
					vi e;
					for (auto it : ed)
						if (it != ind)
							e.pb(it);
					rs.pb(mp(count_common_roads(e),ind));
				}
				for (auto a : E) 
					if (was[a] <= 1) {
						vi e;
						for (auto it : ed)
							if (it != a)
								e.pb(it);
						rs.pb(mp(count_common_roads(e),a));
					}
				int mn = min_element(all(rs))->fi;
				int mx = max_element(all(rs))->fi;
				if (mn == mx) {
					for (auto it : rs)
						if (was[it.se] == 1)
							was[it.se] = 3;
				} else {
					for (auto it : rs)
						if (was[it.se] == 1 && it.fi == mn)
							was[it.se] = 2;
						else
						if (was[it.se] == 1 && it.fi != mn)
							was[it.se] = 3;
				}
			}
		}
	for (auto it : ee)
		s[u[it]][v[it]] = s[v[it]][u[it]] = (was[it] != 3) ? 1 : 0;
	for (int i = 0;i < n;++i) {
		int deg = 0;
		vi e;
		int cnt1 = 0;
		for (int l = 0;l < n;++l)
			p[l] = l;
		for (int j = 0;j < n;++j)
			if (i != j && w[i][j] != -1)
				e.pb(w[i][j]),cnt1 += s[i][j] == 1,p[get(i)] = get(j);
		for (auto it : ee)
			if (get(u[it]) != get(v[it])) {
				p[get(u[it])] = get(v[it]);
				cnt1 += s[u[it]][v[it]] == 1;
				e.pb(it);
			}
		int cnt2 = count_common_roads(e);
		deg = cnt2 - cnt1;
		vi mk;
		for (int k = 1;k <= deg;++k) {
			int t = 0;
			for (int d = 1 << 9;d;d /= 2)
				if (t + d < n) {
					vi e;
					for (int l = 0;l < n;++l)
						p[l] = l;
					int cnt1 = 0;
					for (int j = 0;j < t + d;++j)
						if (j != i && w[i][j] != -1)
							e.pb(w[i][j]),cnt1 += s[i][j] == 1,p[get(j)] = get(i);
					for (auto it : ee)
						if (get(u[it]) != get(v[it])) {
							cnt1 += s[u[it]][v[it]] == 1;
							p[get(u[it])] = get(v[it]);
							e.pb(it);
						}
					int cnt2 = count_common_roads(e);
					if (cnt2 - cnt1 < k)
						t += d;
				}
			mk.pb(t);
		}
		for (auto it : mk)
			s[it][i] = s[i][it] = 1;
	}
	for (int i = 0;i < n;++i)
		for (int j = 0;j < i;++j)
			if (s[i][j] == 1)
				answer.pb(w[i][j]);
	return answer;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i < E.size();++i)
                    ~~^~~~~~~~~~
simurgh.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i < E.size();++i)
                    ~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8624 KB correct
2 Correct 10 ms 8680 KB correct
3 Correct 12 ms 8680 KB correct
4 Correct 9 ms 8680 KB correct
5 Correct 10 ms 8712 KB correct
6 Correct 9 ms 8716 KB correct
7 Correct 2 ms 8716 KB correct
8 Correct 10 ms 8748 KB correct
9 Correct 8 ms 8752 KB correct
10 Correct 10 ms 8772 KB correct
11 Correct 8 ms 8776 KB correct
12 Correct 9 ms 8776 KB correct
13 Correct 12 ms 8784 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8624 KB correct
2 Correct 10 ms 8680 KB correct
3 Correct 12 ms 8680 KB correct
4 Correct 9 ms 8680 KB correct
5 Correct 10 ms 8712 KB correct
6 Correct 9 ms 8716 KB correct
7 Correct 2 ms 8716 KB correct
8 Correct 10 ms 8748 KB correct
9 Correct 8 ms 8752 KB correct
10 Correct 10 ms 8772 KB correct
11 Correct 8 ms 8776 KB correct
12 Correct 9 ms 8776 KB correct
13 Correct 12 ms 8784 KB correct
14 Correct 12 ms 8788 KB correct
15 Correct 12 ms 8800 KB correct
16 Correct 14 ms 8804 KB correct
17 Correct 14 ms 8856 KB correct
18 Correct 13 ms 8864 KB correct
19 Correct 16 ms 8940 KB correct
20 Correct 14 ms 8952 KB correct
21 Correct 12 ms 8952 KB correct
22 Correct 10 ms 8952 KB correct
23 Correct 10 ms 8952 KB correct
24 Correct 11 ms 8952 KB correct
25 Correct 14 ms 8952 KB correct
26 Correct 13 ms 8952 KB correct
27 Correct 10 ms 8952 KB correct
28 Correct 10 ms 8952 KB correct
29 Correct 12 ms 8952 KB correct
30 Correct 13 ms 8952 KB correct
31 Correct 10 ms 8952 KB correct
32 Correct 11 ms 8952 KB correct
33 Correct 12 ms 8952 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8624 KB correct
2 Correct 10 ms 8680 KB correct
3 Correct 12 ms 8680 KB correct
4 Correct 9 ms 8680 KB correct
5 Correct 10 ms 8712 KB correct
6 Correct 9 ms 8716 KB correct
7 Correct 2 ms 8716 KB correct
8 Correct 10 ms 8748 KB correct
9 Correct 8 ms 8752 KB correct
10 Correct 10 ms 8772 KB correct
11 Correct 8 ms 8776 KB correct
12 Correct 9 ms 8776 KB correct
13 Correct 12 ms 8784 KB correct
14 Correct 12 ms 8788 KB correct
15 Correct 12 ms 8800 KB correct
16 Correct 14 ms 8804 KB correct
17 Correct 14 ms 8856 KB correct
18 Correct 13 ms 8864 KB correct
19 Correct 16 ms 8940 KB correct
20 Correct 14 ms 8952 KB correct
21 Correct 12 ms 8952 KB correct
22 Correct 10 ms 8952 KB correct
23 Correct 10 ms 8952 KB correct
24 Correct 11 ms 8952 KB correct
25 Correct 14 ms 8952 KB correct
26 Correct 13 ms 8952 KB correct
27 Correct 10 ms 8952 KB correct
28 Correct 10 ms 8952 KB correct
29 Correct 12 ms 8952 KB correct
30 Correct 13 ms 8952 KB correct
31 Correct 10 ms 8952 KB correct
32 Correct 11 ms 8952 KB correct
33 Correct 12 ms 8952 KB correct
34 Correct 156 ms 9652 KB correct
35 Correct 176 ms 9912 KB correct
36 Correct 144 ms 9912 KB correct
37 Correct 46 ms 9912 KB correct
38 Correct 208 ms 10188 KB correct
39 Correct 163 ms 10316 KB correct
40 Correct 141 ms 10316 KB correct
41 Correct 151 ms 10700 KB correct
42 Correct 175 ms 10892 KB correct
43 Correct 70 ms 10892 KB correct
44 Correct 52 ms 10892 KB correct
45 Correct 58 ms 10964 KB correct
46 Correct 48 ms 10964 KB correct
47 Correct 38 ms 10964 KB correct
48 Correct 17 ms 11052 KB correct
49 Correct 22 ms 11052 KB correct
50 Correct 28 ms 11076 KB correct
51 Correct 69 ms 11244 KB correct
52 Correct 53 ms 11244 KB correct
53 Correct 43 ms 11300 KB correct
54 Correct 65 ms 11568 KB correct
55 Correct 83 ms 11744 KB correct
56 Correct 89 ms 11860 KB correct
57 Correct 94 ms 11860 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11860 KB correct
2 Correct 10 ms 11860 KB correct
3 Correct 703 ms 13436 KB correct
4 Correct 1036 ms 15240 KB correct
5 Correct 1250 ms 16088 KB correct
6 Correct 1204 ms 16960 KB correct
7 Correct 1183 ms 17336 KB correct
8 Correct 1379 ms 17336 KB correct
9 Correct 1054 ms 17488 KB correct
10 Correct 1132 ms 17488 KB correct
11 Correct 1272 ms 17488 KB correct
12 Correct 1128 ms 17488 KB correct
13 Correct 10 ms 17488 KB correct
14 Correct 1138 ms 17488 KB correct
15 Correct 1088 ms 17488 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8624 KB correct
2 Correct 10 ms 8680 KB correct
3 Correct 12 ms 8680 KB correct
4 Correct 9 ms 8680 KB correct
5 Correct 10 ms 8712 KB correct
6 Correct 9 ms 8716 KB correct
7 Correct 2 ms 8716 KB correct
8 Correct 10 ms 8748 KB correct
9 Correct 8 ms 8752 KB correct
10 Correct 10 ms 8772 KB correct
11 Correct 8 ms 8776 KB correct
12 Correct 9 ms 8776 KB correct
13 Correct 12 ms 8784 KB correct
14 Correct 12 ms 8788 KB correct
15 Correct 12 ms 8800 KB correct
16 Correct 14 ms 8804 KB correct
17 Correct 14 ms 8856 KB correct
18 Correct 13 ms 8864 KB correct
19 Correct 16 ms 8940 KB correct
20 Correct 14 ms 8952 KB correct
21 Correct 12 ms 8952 KB correct
22 Correct 10 ms 8952 KB correct
23 Correct 10 ms 8952 KB correct
24 Correct 11 ms 8952 KB correct
25 Correct 14 ms 8952 KB correct
26 Correct 13 ms 8952 KB correct
27 Correct 10 ms 8952 KB correct
28 Correct 10 ms 8952 KB correct
29 Correct 12 ms 8952 KB correct
30 Correct 13 ms 8952 KB correct
31 Correct 10 ms 8952 KB correct
32 Correct 11 ms 8952 KB correct
33 Correct 12 ms 8952 KB correct
34 Correct 156 ms 9652 KB correct
35 Correct 176 ms 9912 KB correct
36 Correct 144 ms 9912 KB correct
37 Correct 46 ms 9912 KB correct
38 Correct 208 ms 10188 KB correct
39 Correct 163 ms 10316 KB correct
40 Correct 141 ms 10316 KB correct
41 Correct 151 ms 10700 KB correct
42 Correct 175 ms 10892 KB correct
43 Correct 70 ms 10892 KB correct
44 Correct 52 ms 10892 KB correct
45 Correct 58 ms 10964 KB correct
46 Correct 48 ms 10964 KB correct
47 Correct 38 ms 10964 KB correct
48 Correct 17 ms 11052 KB correct
49 Correct 22 ms 11052 KB correct
50 Correct 28 ms 11076 KB correct
51 Correct 69 ms 11244 KB correct
52 Correct 53 ms 11244 KB correct
53 Correct 43 ms 11300 KB correct
54 Correct 65 ms 11568 KB correct
55 Correct 83 ms 11744 KB correct
56 Correct 89 ms 11860 KB correct
57 Correct 94 ms 11860 KB correct
58 Correct 2 ms 11860 KB correct
59 Correct 10 ms 11860 KB correct
60 Correct 703 ms 13436 KB correct
61 Correct 1036 ms 15240 KB correct
62 Correct 1250 ms 16088 KB correct
63 Correct 1204 ms 16960 KB correct
64 Correct 1183 ms 17336 KB correct
65 Correct 1379 ms 17336 KB correct
66 Correct 1054 ms 17488 KB correct
67 Correct 1132 ms 17488 KB correct
68 Correct 1272 ms 17488 KB correct
69 Correct 1128 ms 17488 KB correct
70 Correct 10 ms 17488 KB correct
71 Correct 1138 ms 17488 KB correct
72 Correct 1088 ms 17488 KB correct
73 Correct 2 ms 17488 KB correct
74 Correct 1231 ms 18400 KB correct
75 Correct 1230 ms 19128 KB correct
76 Correct 415 ms 19128 KB correct
77 Correct 1220 ms 20548 KB correct
78 Correct 1190 ms 21488 KB correct
79 Correct 1200 ms 22352 KB correct
80 Correct 1126 ms 23128 KB correct
81 Correct 1012 ms 23668 KB correct
82 Correct 1119 ms 24912 KB correct
83 Correct 746 ms 24912 KB correct
84 Correct 599 ms 24912 KB correct
85 Correct 518 ms 25304 KB correct
86 Correct 251 ms 25376 KB correct
87 Correct 185 ms 25512 KB correct
88 Correct 151 ms 25616 KB correct
89 Correct 128 ms 25676 KB correct
90 Correct 120 ms 25752 KB correct
91 Correct 34 ms 25752 KB correct
92 Correct 35 ms 25752 KB correct
93 Correct 400 ms 26924 KB correct
94 Correct 325 ms 26924 KB correct
95 Correct 309 ms 27228 KB correct
96 Correct 121 ms 27228 KB correct
97 Correct 142 ms 27364 KB correct
98 Correct 171 ms 27628 KB correct
99 Correct 147 ms 27748 KB correct
100 Correct 66 ms 27748 KB correct
101 Correct 36 ms 27748 KB correct
102 Correct 601 ms 29032 KB correct
103 Correct 476 ms 29372 KB correct
104 Correct 676 ms 29824 KB correct
105 Correct 510 ms 30164 KB correct