oj.uz

Submission #283922

# Submission time Handle Problem Language Result Execution time Memory
283922 2020-08-26T09:40:39 Z erd1 Simurgh (IOI17_simurgh) C++14
100 / 100
 293 ms 7080 KB 
#include "simurgh.h"

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
typedef pair<int, int> pii;
typedef long long lld;
typedef long double ld;

template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
	for(Iter i = b; i != e; ++i)
		out << (i == b?"":" ") << *i;
	return out;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
	return out << '(' << p.ff << ", " << p.ss << ')';
}
template<typename T>
ostream& operator<<(ostream& out, vector<T> v){
	return outIt(out << '[', all(v)) << ']';
}


vector<vector<pii>> G;
vector<bool> asked, ans;
vector<int> te, es, dep, par, pe;
vector<pii> Edges;
//int c = 0;
int dfs(int i, int d = 1){
	//cout << i << " " << d << " " << par[i] << endl;
	//if(c++>100)exit(-1);
	dep[i] = d;
	int minup = d;
	for(auto x : G[i]){
		if(x.ss == pe[i])continue;
		if(dep[x.ff]){
			//cout << "counter" << x << endl;
			minup = min(minup, dep[x.ff]);
			continue;
		}
		es.pb(x.ss);
		te[x.ss] = es.size();
		pe[x.ff] = x.ss; par[x.ff] = i;
		minup = min(minup, dfs(x.ff, d + 1));
	}
	if(!i)return 0;
	//cout << i << minup << endl;
	if(minup == d){
		ans[pe[i]] = true;
		asked[pe[i]] = true;
	}
	return minup;
}

int asking(int tree, int nontree){
	//cout << "ask " << tree << " " << nontree << endl;
	swap(es[te[tree]-1], nontree);
	int ansx = count_common_roads(es);
	swap(es[te[tree]-1], nontree);
	//cout << ansx << endl;
	return ansx;
}

vector<int> dsu;
int root(int i){ return i == dsu[i] ? i : (dsu[i] = root(dsu[i])); }
inline bool join(int i, int j){ i = root(i), j = root(j); if(i == j)return false; dsu[i] = j; return true; }

int ask2(vector<int>& v){
	//cout << v << es << endl;
	iota(all(dsu), 0);
	int mm = v.size(), cnt = 0;
	for(auto i: v)assert(join(Edges[i].ff, Edges[i].ss));
	//cout << "gh" << endl;
	for(auto i: es)
		if(join(Edges[i].ff, Edges[i].ss))
			cnt += ans[i], v.pb(i);
	int ret = count_common_roads(v);
	v.resize(mm);
	return ret - cnt;
}

void process(int k){
	vector<int> gt, a;
	for(auto x: G[k])
		if(!asked[x.ss])gt.pb(x.ss);
	if(gt.size() == 0)return;
	int deg = ask2(gt);
	//cout << "process" << k << endl;
	//for(auto i: gt)cout << Edges[i]; cout << endl;
	//cout << deg << endl;
	for(int i = 0; i < deg; i++){
		int l = 0, r = gt.size();
		while(r-l > 1){
			a.resize(0);
			for(int j = 0; j < (l+r>>1); j++)a.pb(gt[j]);
			(ask2(a) <= i?l:r) = l+r>>1;
		}
		ans[gt[l]] = true;
	}
	for(auto i: gt)asked[i] = true;
	//cout << asked << endl << ans << endl << endl;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m = u.size();
	te.resize(m); asked.resize(m); ans.resize(m); pe.resize(n); par.resize(n); dep.resize(n); pe[0] = -1; dsu.resize(n);
	G.resize(n);
	for(int i = 0; i < m; i++)Edges.pb({u[i], v[i]});
	for(int i = 0; i < m; i++)G[u[i]].pb({v[i], i}), G[v[i]].pb({u[i], i});
	dfs(0);
	int tans = count_common_roads(es);
	//cout << tans << endl;
	//cout << asked << endl;
	//cout << te << es << dep << par << endl;
	for(int i = 0; i < m; i++) if(dep[u[i]] < dep[v[i]])swap(u[i], v[i]);
	for(int i = 0; i < m; i++)
		if(!te[i]){
			//cout << i << endl;
			int tt = -1, go = false;
			for(int c = u[i]; c != v[i]; c = par[c]){
				if(asked[pe[c]])tt = pe[c];
				else go = true;
			}
			if(!go)continue;

			if(tt != -1){
				{
					int cans = asking(tt, i);
					if(cans == tans)ans[i] = ans[tt];
					else if(cans < tans)ans[i] = false, assert(ans[tt] == true);
					else if(cans > tans)ans[i] = true, assert(ans[tt] == false);
					asked[i] = true;
				}
				for(int c = u[i]; c != v[i]; c = par[c])
					if(!asked[pe[c]]){
						int cans = asking(pe[c], i);
						if(cans == tans)ans[pe[c]] = ans[i];
						else if(cans < tans)ans[pe[c]] = true;
						else if(cans > tans)ans[i] = true;
						asked[pe[c]] = true;
					}
			}else{
				for(int c = u[i]; c != v[i]; c = par[c])
					if(!asked[pe[c]]){
						int cans = asking(pe[c], i);
						if(cans < tans)ans[pe[c]] = true;
						else if(cans > tans)ans[i] = true;
						if(cans != tans)asked[pe[c]] = asked[i] = true;
					}
				asked[i] = true;
				for(int c = u[i]; c != v[i]; c = par[c])
					if(!asked[pe[c]]) ans[pe[c]] = ans[i], asked[pe[c]] = true;
			}
		}
	//cout << asked << endl << ans << endl;
	for(int i = 0; i < n; i++)process(i);

	//cout << asked << endl << ans << endl;
	vector<int> ret;
	for(int i = 0; i < m; i++){
		assert(asked[i]);
		if(ans[i])ret.pb(i);
	}
	//assert(ret.size() == n-1);
	return ret;
}

Compilation message

simurgh.cpp: In function 'void process(int)':
simurgh.cpp:100:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |    for(int j = 0; j < (l+r>>1); j++)a.pb(gt[j]);
      |                        ~^~
simurgh.cpp:101:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |    (ask2(a) <= i?l:r) = l+r>>1;
      |                         ~^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 1 ms 256 KB correct
3 Correct 1 ms 256 KB correct
4 Correct 1 ms 256 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 1 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 0 ms 256 KB correct
12 Correct 1 ms 256 KB correct
13 Correct 1 ms 256 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 1 ms 256 KB correct
3 Correct 1 ms 256 KB correct
4 Correct 1 ms 256 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 1 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 0 ms 256 KB correct
12 Correct 1 ms 256 KB correct
13 Correct 1 ms 256 KB correct
14 Correct 2 ms 384 KB correct
15 Correct 2 ms 384 KB correct
16 Correct 2 ms 384 KB correct
17 Correct 2 ms 384 KB correct
18 Correct 1 ms 384 KB correct
19 Correct 2 ms 384 KB correct
20 Correct 2 ms 384 KB correct
21 Correct 3 ms 384 KB correct
22 Correct 2 ms 384 KB correct
23 Correct 1 ms 384 KB correct
24 Correct 1 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 1 ms 384 KB correct
27 Correct 1 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 1 ms 384 KB correct
31 Correct 1 ms 384 KB correct
32 Correct 1 ms 384 KB correct
33 Correct 1 ms 384 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 1 ms 256 KB correct
3 Correct 1 ms 256 KB correct
4 Correct 1 ms 256 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 1 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 0 ms 256 KB correct
12 Correct 1 ms 256 KB correct
13 Correct 1 ms 256 KB correct
14 Correct 2 ms 384 KB correct
15 Correct 2 ms 384 KB correct
16 Correct 2 ms 384 KB correct
17 Correct 2 ms 384 KB correct
18 Correct 1 ms 384 KB correct
19 Correct 2 ms 384 KB correct
20 Correct 2 ms 384 KB correct
21 Correct 3 ms 384 KB correct
22 Correct 2 ms 384 KB correct
23 Correct 1 ms 384 KB correct
24 Correct 1 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 1 ms 384 KB correct
27 Correct 1 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 1 ms 384 KB correct
31 Correct 1 ms 384 KB correct
32 Correct 1 ms 384 KB correct
33 Correct 1 ms 384 KB correct
34 Correct 52 ms 1920 KB correct
35 Correct 53 ms 1792 KB correct
36 Correct 40 ms 1536 KB correct
37 Correct 9 ms 384 KB correct
38 Correct 51 ms 1920 KB correct
39 Correct 45 ms 1664 KB correct
40 Correct 47 ms 1536 KB correct
41 Correct 47 ms 1920 KB correct
42 Correct 56 ms 1920 KB correct
43 Correct 21 ms 1280 KB correct
44 Correct 16 ms 1024 KB correct
45 Correct 17 ms 1148 KB correct
46 Correct 15 ms 1000 KB correct
47 Correct 9 ms 640 KB correct
48 Correct 3 ms 416 KB correct
49 Correct 7 ms 384 KB correct
50 Correct 9 ms 640 KB correct
51 Correct 24 ms 1148 KB correct
52 Correct 15 ms 1024 KB correct
53 Correct 14 ms 896 KB correct
54 Correct 23 ms 1280 KB correct
55 Correct 18 ms 1152 KB correct
56 Correct 18 ms 1152 KB correct
57 Correct 23 ms 1128 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 154 ms 4844 KB correct
4 Correct 271 ms 7020 KB correct
5 Correct 287 ms 7020 KB correct
6 Correct 260 ms 7080 KB correct
7 Correct 280 ms 6996 KB correct
8 Correct 253 ms 7044 KB correct
9 Correct 273 ms 7020 KB correct
10 Correct 287 ms 7020 KB correct
11 Correct 287 ms 7060 KB correct
12 Correct 292 ms 7064 KB correct
13 Correct 1 ms 256 KB correct
14 Correct 277 ms 6996 KB correct
15 Correct 286 ms 7052 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 1 ms 256 KB correct
3 Correct 1 ms 256 KB correct
4 Correct 1 ms 256 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 1 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 0 ms 256 KB correct
12 Correct 1 ms 256 KB correct
13 Correct 1 ms 256 KB correct
14 Correct 2 ms 384 KB correct
15 Correct 2 ms 384 KB correct
16 Correct 2 ms 384 KB correct
17 Correct 2 ms 384 KB correct
18 Correct 1 ms 384 KB correct
19 Correct 2 ms 384 KB correct
20 Correct 2 ms 384 KB correct
21 Correct 3 ms 384 KB correct
22 Correct 2 ms 384 KB correct
23 Correct 1 ms 384 KB correct
24 Correct 1 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 1 ms 384 KB correct
27 Correct 1 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 1 ms 384 KB correct
31 Correct 1 ms 384 KB correct
32 Correct 1 ms 384 KB correct
33 Correct 1 ms 384 KB correct
34 Correct 52 ms 1920 KB correct
35 Correct 53 ms 1792 KB correct
36 Correct 40 ms 1536 KB correct
37 Correct 9 ms 384 KB correct
38 Correct 51 ms 1920 KB correct
39 Correct 45 ms 1664 KB correct
40 Correct 47 ms 1536 KB correct
41 Correct 47 ms 1920 KB correct
42 Correct 56 ms 1920 KB correct
43 Correct 21 ms 1280 KB correct
44 Correct 16 ms 1024 KB correct
45 Correct 17 ms 1148 KB correct
46 Correct 15 ms 1000 KB correct
47 Correct 9 ms 640 KB correct
48 Correct 3 ms 416 KB correct
49 Correct 7 ms 384 KB correct
50 Correct 9 ms 640 KB correct
51 Correct 24 ms 1148 KB correct
52 Correct 15 ms 1024 KB correct
53 Correct 14 ms 896 KB correct
54 Correct 23 ms 1280 KB correct
55 Correct 18 ms 1152 KB correct
56 Correct 18 ms 1152 KB correct
57 Correct 23 ms 1128 KB correct
58 Correct 1 ms 256 KB correct
59 Correct 1 ms 384 KB correct
60 Correct 154 ms 4844 KB correct
61 Correct 271 ms 7020 KB correct
62 Correct 287 ms 7020 KB correct
63 Correct 260 ms 7080 KB correct
64 Correct 280 ms 6996 KB correct
65 Correct 253 ms 7044 KB correct
66 Correct 273 ms 7020 KB correct
67 Correct 287 ms 7020 KB correct
68 Correct 287 ms 7060 KB correct
69 Correct 292 ms 7064 KB correct
70 Correct 1 ms 256 KB correct
71 Correct 277 ms 6996 KB correct
72 Correct 286 ms 7052 KB correct
73 Correct 0 ms 256 KB correct
74 Correct 285 ms 7044 KB correct
75 Correct 277 ms 6872 KB correct
76 Correct 122 ms 2904 KB correct
77 Correct 267 ms 7036 KB correct
78 Correct 287 ms 7052 KB correct
79 Correct 293 ms 7040 KB correct
80 Correct 282 ms 7020 KB correct
81 Correct 239 ms 6252 KB correct
82 Correct 270 ms 6892 KB correct
83 Correct 206 ms 3960 KB correct
84 Correct 97 ms 4724 KB correct
85 Correct 94 ms 4472 KB correct
86 Correct 70 ms 2936 KB correct
87 Correct 57 ms 2432 KB correct
88 Correct 49 ms 1792 KB correct
89 Correct 54 ms 1792 KB correct
90 Correct 43 ms 1536 KB correct
91 Correct 19 ms 512 KB correct
92 Correct 10 ms 384 KB correct
93 Correct 85 ms 4468 KB correct
94 Correct 64 ms 2936 KB correct
95 Correct 62 ms 2936 KB correct
96 Correct 40 ms 1664 KB correct
97 Correct 48 ms 1792 KB correct
98 Correct 47 ms 2520 KB correct
99 Correct 48 ms 1792 KB correct
100 Correct 22 ms 768 KB correct
101 Correct 12 ms 384 KB correct
102 Correct 118 ms 3696 KB correct
103 Correct 117 ms 3824 KB correct
104 Correct 96 ms 3704 KB correct
105 Correct 113 ms 3696 KB correct