oj.uz

Submission #42847

# Submission time Handle Problem Language Result Execution time Memory
42847 2018-03-04T20:32:04 Z alenam0161 Simurgh (IOI17_simurgh) C++14
100 / 100
 352 ms 30356 KB 
#include "simurgh.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cassert>
using namespace std;
#define DG(x) for(int i=0;i<(x).size();++i)cerr<<x[i]<<", ";
const int N = 1e3 + 7;
int used[N];
struct edge {
	int ham, x;
};
vector<edge> g[N], ham[N],Nor[N];
void pr(vector<edge> Tp) {
	for (edge to : Tp) {
		cout << "h=" << to.ham << "and v=" << to.x << ", ";
	}
	cout << endl;
}
vector<int> V, U;
bool is_it_in_T[N*N],Found[N*N];
int arj[N],Q[N];
int How[N*N];
int di[N];
int n,m;
void get_any(int v, vector<int> &T) {
	used[v] = true;
	for (auto to:g[v]) {
		if (used[to.x])continue;
		di[to.x] = di[v] + 1;
		T.push_back(to.ham);
		is_it_in_T[to.ham] = true;
		get_any(to.x, T);
	}
}
int par[N];
int find_par(int v) {
	return (v == par[v] ? v : par[v] = find_par(par[v]));
}
void Merge(int v, int u) {
	v = find_par(v);
	u = find_par(u);
	if (u != v) {
		if (rand() & 1)par[v] = u;
		else par[u] = v;
	}
}
int Newspantree(vector<int> &cur,vector<int> &T) {
	for (int i = 0; i < n; ++i)par[i] = i;
	for (int i = 0; i < cur.size(); ++i)Merge(V[cur[i]], U[cur[i]]);
	int hw = 0;
	for (int i = 0; i < T.size(); ++i) {
		if (find_par(V[T[i]]) == find_par(U[T[i]]))continue;
		Merge(V[T[i]], U[T[i]]);
		cur.push_back(T[i]);
		hw+=Found[T[i]];
	}
	assert(cur.size() == n - 1);
	return hw;
}
vector<int> Cikl;
int curpar[N];
bool gta;
void find_cik(int v,int G,int p) {
	if (gta == false) {
		used[v] = 1;
		for (edge to : g[v]) {
			if (to.x == p)continue;
			if (gta)return;
			if (used[to.x] == 2)continue;
			if (is_it_in_T[to.ham] == false)continue;
			if (used[to.x] == 0) {
				curpar[to.x] = v;
				Cikl.push_back(to.ham);
				find_cik(to.x, G,v);
				if (gta)return;
				Cikl.pop_back();
			}
			else if (used[to.x] == 1 && to.x == G) {
				Cikl.push_back(to.ham);
				gta = true; return;
			}
		}
		if (gta)return;
		for (edge to : g[v]) {
			if (to.x == p)continue;
			if (used[to.x] == 2)continue;
			if (gta)return;
			if (is_it_in_T[to.ham] == true)continue;
			if (used[to.x] == 0) {
				curpar[to.x] = v;
				Cikl.push_back(to.ham);
				find_cik(to.x, G,v);
				if (gta)return;
				Cikl.pop_back();
			}
			else if (used[to.x] == 1 && to.x == G) {
				Cikl.push_back(to.ham);
				gta = true;return;
			}
		}
		used[v] = 2;
	}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	::n = n; ::m = u.size();
	U = u; V = v;
	for (int i = 0; i < u.size(); ++i) {
		g[u[i]].push_back({ i,v[i] });
		g[v[i]].push_back({ i,u[i] });
	}
	vector<int> ans;
	vector<int> T;
	vector<int> val;
	memset(used, 0, sizeof(used));
	get_any(0, T);
	int ct = count_common_roads(T);
	for (int i = 0; i < u.size(); ++i) {
		if (is_it_in_T[i] == true) {
			if (How[i])continue;
			How[i] = true;
			memset(used, 0, sizeof(used));
			Cikl.clear();
			gta = false;
			Cikl.push_back(i);
			used[(di[u[i]] <= di[v[i]] ? u[i] : v[i])] =1;
			find_cik((di[u[i]] >= di[v[i]] ? u[i] : v[i]),( di[u[i]] <= di[v[i]] ? u[i] : v[i]), (di[u[i]] <= di[v[i]] ? u[i] : v[i]));
			val.resize(Cikl.size(), 0);
			for (int ii = 0; ii < Cikl.size(); ++ii) {
				vector<int> cur;
				for (int j = 0; j < Cikl.size(); ++j) {
					if (ii != j)cur.push_back(Cikl[j]);
				}
				Newspantree(cur, T);
				val[ii] = count_common_roads(cur);
			}
			int mx = -1e9;int mn = 1e9;
			for (int ii = 0; ii < Cikl.size(); ++ii) {
				mx = max(mx, val[ii]);
				mn = min(mn, val[ii]);
				How[Cikl[ii]] = true;
			}
			if (mx == mn) {
				for (int ii = 0; ii < Cikl.size(); ++ii) {
					Found[Cikl[ii]] = Cikl.size()<3;
				}
			}
			else {
				for (int ii = 0; ii < Cikl.size(); ++ii) {
					if(mn==val[ii])
					Found[Cikl[ii]] = 1;
					else 
					Found[Cikl[ii]] = 0;
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		vector<int> e;
		for (auto to : g[i])e.push_back(to.ham);
		int k=Newspantree(e, T);
		int gt = count_common_roads(e);
		arj[i] = gt - k;
		Q[i] = gt - k;
	}
	for (int i = 0; i < m; ++i) {
		if (Found[i] == 1) {
			Q[v[i]]--;
			arj[u[i]]--;
			Q[u[i]]--;
			arj[v[i]]--;
		}
	}
	memset(used, 0, sizeof(used));
	for (int i = 0; i < n; ++i) {
		int ps = -1;
		for (int j = 0; j < n; ++j) {
			if (arj[j] == 1 && used[j] == 0) {
				ps = j; break;
			}
		}
		if (ps == -1)break;
		used[ps] = true;
		int hw = 0;
	//	cerr <<"vertex number:"<<i<<" is "<< ps << endl;
		int q = 0;
		for(edge to:g[ps]){
			if (How[to.ham] == true) {
				hw += Found[to.ham];
			}
			else {
				q++;
			}
		}
		int l = 0, r = q-1;
		int mid = l;
		int good = l;
		while (l <= r) {
			mid = (l + r) / 2;
			vector<int> el,er;
			int s = 0;
			int ok = 0;
			for (edge to : g[ps]) {
				if (How[to.ham] == true) {
					continue;
				}
				else {
					if (l <= s && s <= mid) {
						el.push_back(to.ham);
					}
					else if(mid+1<=s&&s<=r){
						er.push_back(to.ham);
					}
					s++;
				}
			}
			int x1=Newspantree(el, T);
			if (count_common_roads(el)-x1 == 1) {
				good = mid; r = mid-1;
			}
			else {
				 l = mid + 1;
			}
		}
		int s = 0;
		int ok = 0;
		for (edge to : g[ps]) {
			if (How[to.ham] == true) {
			}
			else {
				if (s==good) {
					arj[to.x]--;
					How[to.ham] = 1;
					Found[to.ham] = 1;
				}
				s++;
			}
		}
	}
	ans.clear();
	for (int i = 0; i < m; ++i) {
		if (Found[i] == 1)ans.push_back(i);
	}
//	DG(ans);
//	cout << endl;
	return ans;
}

Compilation message

simurgh.cpp: In function 'int Newspantree(std::vector<int>&, std::vector<int>&)':
simurgh.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cur.size(); ++i)Merge(V[cur[i]], U[cur[i]]);
                    ^
simurgh.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); ++i) {
                    ^
In file included from /usr/include/c++/5/cassert:43:0,
                 from simurgh.cpp:5:
simurgh.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(cur.size() == n - 1);
                    ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < u.size(); ++i) {
                    ^
simurgh.cpp:118:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < u.size(); ++i) {
                    ^
simurgh.cpp:129:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int ii = 0; ii < Cikl.size(); ++ii) {
                        ^
simurgh.cpp:131:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < Cikl.size(); ++j) {
                       ^
simurgh.cpp:138:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int ii = 0; ii < Cikl.size(); ++ii) {
                        ^
simurgh.cpp:144:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii = 0; ii < Cikl.size(); ++ii) {
                         ^
simurgh.cpp:149:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii = 0; ii < Cikl.size(); ++ii) {
                         ^
simurgh.cpp:202:8: warning: unused variable 'ok' [-Wunused-variable]
    int ok = 0;
        ^
simurgh.cpp:226:7: warning: unused variable 'ok' [-Wunused-variable]
   int ok = 0;
       ^
simurgh.cpp:117:6: warning: unused variable 'ct' [-Wunused-variable]
  int ct = count_common_roads(T);
      ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 480 KB correct
3 Correct 2 ms 480 KB correct
4 Correct 2 ms 680 KB correct
5 Correct 2 ms 680 KB correct
6 Correct 2 ms 680 KB correct
7 Correct 2 ms 680 KB correct
8 Correct 2 ms 680 KB correct
9 Correct 2 ms 680 KB correct
10 Correct 2 ms 688 KB correct
11 Correct 2 ms 688 KB correct
12 Correct 2 ms 688 KB correct
13 Correct 2 ms 688 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 480 KB correct
3 Correct 2 ms 480 KB correct
4 Correct 2 ms 680 KB correct
5 Correct 2 ms 680 KB correct
6 Correct 2 ms 680 KB correct
7 Correct 2 ms 680 KB correct
8 Correct 2 ms 680 KB correct
9 Correct 2 ms 680 KB correct
10 Correct 2 ms 688 KB correct
11 Correct 2 ms 688 KB correct
12 Correct 2 ms 688 KB correct
13 Correct 2 ms 688 KB correct
14 Correct 4 ms 732 KB correct
15 Correct 4 ms 732 KB correct
16 Correct 4 ms 740 KB correct
17 Correct 4 ms 796 KB correct
18 Correct 3 ms 852 KB correct
19 Correct 4 ms 872 KB correct
20 Correct 4 ms 896 KB correct
21 Correct 4 ms 952 KB correct
22 Correct 2 ms 960 KB correct
23 Correct 3 ms 968 KB correct
24 Correct 2 ms 1100 KB correct
25 Correct 2 ms 1100 KB correct
26 Correct 3 ms 1100 KB correct
27 Correct 3 ms 1100 KB correct
28 Correct 2 ms 1100 KB correct
29 Correct 3 ms 1100 KB correct
30 Correct 3 ms 1100 KB correct
31 Correct 2 ms 1100 KB correct
32 Correct 3 ms 1100 KB correct
33 Correct 3 ms 1100 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 480 KB correct
3 Correct 2 ms 480 KB correct
4 Correct 2 ms 680 KB correct
5 Correct 2 ms 680 KB correct
6 Correct 2 ms 680 KB correct
7 Correct 2 ms 680 KB correct
8 Correct 2 ms 680 KB correct
9 Correct 2 ms 680 KB correct
10 Correct 2 ms 688 KB correct
11 Correct 2 ms 688 KB correct
12 Correct 2 ms 688 KB correct
13 Correct 2 ms 688 KB correct
14 Correct 4 ms 732 KB correct
15 Correct 4 ms 732 KB correct
16 Correct 4 ms 740 KB correct
17 Correct 4 ms 796 KB correct
18 Correct 3 ms 852 KB correct
19 Correct 4 ms 872 KB correct
20 Correct 4 ms 896 KB correct
21 Correct 4 ms 952 KB correct
22 Correct 2 ms 960 KB correct
23 Correct 3 ms 968 KB correct
24 Correct 2 ms 1100 KB correct
25 Correct 2 ms 1100 KB correct
26 Correct 3 ms 1100 KB correct
27 Correct 3 ms 1100 KB correct
28 Correct 2 ms 1100 KB correct
29 Correct 3 ms 1100 KB correct
30 Correct 3 ms 1100 KB correct
31 Correct 2 ms 1100 KB correct
32 Correct 3 ms 1100 KB correct
33 Correct 3 ms 1100 KB correct
34 Correct 64 ms 2464 KB correct
35 Correct 60 ms 2708 KB correct
36 Correct 60 ms 2708 KB correct
37 Correct 67 ms 2708 KB correct
38 Correct 56 ms 3012 KB correct
39 Correct 59 ms 3060 KB correct
40 Correct 63 ms 3084 KB correct
41 Correct 106 ms 3604 KB correct
42 Correct 55 ms 3920 KB correct
43 Correct 33 ms 3920 KB correct
44 Correct 29 ms 3920 KB correct
45 Correct 29 ms 3920 KB correct
46 Correct 24 ms 3920 KB correct
47 Correct 19 ms 3920 KB correct
48 Correct 10 ms 3920 KB correct
49 Correct 26 ms 3920 KB correct
50 Correct 19 ms 3920 KB correct
51 Correct 36 ms 3920 KB correct
52 Correct 32 ms 3920 KB correct
53 Correct 32 ms 3920 KB correct
54 Correct 27 ms 4088 KB correct
55 Correct 30 ms 4088 KB correct
56 Correct 27 ms 4088 KB correct
57 Correct 33 ms 4276 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4276 KB correct
2 Correct 2 ms 4276 KB correct
3 Correct 200 ms 7668 KB correct
4 Correct 262 ms 10396 KB correct
5 Correct 297 ms 11324 KB correct
6 Correct 272 ms 12312 KB correct
7 Correct 292 ms 13308 KB correct
8 Correct 277 ms 14076 KB correct
9 Correct 294 ms 14908 KB correct
10 Correct 316 ms 15928 KB correct
11 Correct 305 ms 16984 KB correct
12 Correct 292 ms 17832 KB correct
13 Correct 2 ms 17832 KB correct
14 Correct 286 ms 18744 KB correct
15 Correct 274 ms 19524 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 480 KB correct
3 Correct 2 ms 480 KB correct
4 Correct 2 ms 680 KB correct
5 Correct 2 ms 680 KB correct
6 Correct 2 ms 680 KB correct
7 Correct 2 ms 680 KB correct
8 Correct 2 ms 680 KB correct
9 Correct 2 ms 680 KB correct
10 Correct 2 ms 688 KB correct
11 Correct 2 ms 688 KB correct
12 Correct 2 ms 688 KB correct
13 Correct 2 ms 688 KB correct
14 Correct 4 ms 732 KB correct
15 Correct 4 ms 732 KB correct
16 Correct 4 ms 740 KB correct
17 Correct 4 ms 796 KB correct
18 Correct 3 ms 852 KB correct
19 Correct 4 ms 872 KB correct
20 Correct 4 ms 896 KB correct
21 Correct 4 ms 952 KB correct
22 Correct 2 ms 960 KB correct
23 Correct 3 ms 968 KB correct
24 Correct 2 ms 1100 KB correct
25 Correct 2 ms 1100 KB correct
26 Correct 3 ms 1100 KB correct
27 Correct 3 ms 1100 KB correct
28 Correct 2 ms 1100 KB correct
29 Correct 3 ms 1100 KB correct
30 Correct 3 ms 1100 KB correct
31 Correct 2 ms 1100 KB correct
32 Correct 3 ms 1100 KB correct
33 Correct 3 ms 1100 KB correct
34 Correct 64 ms 2464 KB correct
35 Correct 60 ms 2708 KB correct
36 Correct 60 ms 2708 KB correct
37 Correct 67 ms 2708 KB correct
38 Correct 56 ms 3012 KB correct
39 Correct 59 ms 3060 KB correct
40 Correct 63 ms 3084 KB correct
41 Correct 106 ms 3604 KB correct
42 Correct 55 ms 3920 KB correct
43 Correct 33 ms 3920 KB correct
44 Correct 29 ms 3920 KB correct
45 Correct 29 ms 3920 KB correct
46 Correct 24 ms 3920 KB correct
47 Correct 19 ms 3920 KB correct
48 Correct 10 ms 3920 KB correct
49 Correct 26 ms 3920 KB correct
50 Correct 19 ms 3920 KB correct
51 Correct 36 ms 3920 KB correct
52 Correct 32 ms 3920 KB correct
53 Correct 32 ms 3920 KB correct
54 Correct 27 ms 4088 KB correct
55 Correct 30 ms 4088 KB correct
56 Correct 27 ms 4088 KB correct
57 Correct 33 ms 4276 KB correct
58 Correct 2 ms 4276 KB correct
59 Correct 2 ms 4276 KB correct
60 Correct 200 ms 7668 KB correct
61 Correct 262 ms 10396 KB correct
62 Correct 297 ms 11324 KB correct
63 Correct 272 ms 12312 KB correct
64 Correct 292 ms 13308 KB correct
65 Correct 277 ms 14076 KB correct
66 Correct 294 ms 14908 KB correct
67 Correct 316 ms 15928 KB correct
68 Correct 305 ms 16984 KB correct
69 Correct 292 ms 17832 KB correct
70 Correct 2 ms 17832 KB correct
71 Correct 286 ms 18744 KB correct
72 Correct 274 ms 19524 KB correct
73 Correct 2 ms 19524 KB correct
74 Correct 352 ms 20720 KB correct
75 Correct 326 ms 21428 KB correct
76 Correct 135 ms 21428 KB correct
77 Correct 288 ms 22896 KB correct
78 Correct 291 ms 23564 KB correct
79 Correct 244 ms 24632 KB correct
80 Correct 278 ms 25368 KB correct
81 Correct 286 ms 25556 KB correct
82 Correct 245 ms 27084 KB correct
83 Correct 244 ms 27084 KB correct
84 Correct 133 ms 27084 KB correct
85 Correct 135 ms 27084 KB correct
86 Correct 117 ms 27084 KB correct
87 Correct 107 ms 27084 KB correct
88 Correct 82 ms 27084 KB correct
89 Correct 94 ms 27084 KB correct
90 Correct 108 ms 27084 KB correct
91 Correct 65 ms 27084 KB correct
92 Correct 40 ms 27084 KB correct
93 Correct 131 ms 27872 KB correct
94 Correct 131 ms 27872 KB correct
95 Correct 105 ms 27872 KB correct
96 Correct 97 ms 27872 KB correct
97 Correct 90 ms 27872 KB correct
98 Correct 104 ms 27872 KB correct
99 Correct 104 ms 27872 KB correct
100 Correct 65 ms 27872 KB correct
101 Correct 170 ms 27872 KB correct
102 Correct 137 ms 29080 KB correct
103 Correct 163 ms 29572 KB correct
104 Correct 123 ms 30068 KB correct
105 Correct 167 ms 30356 KB correct