답안 #58701 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58701	2018-07-18T23:11:34 Z	reality	Simurgh (IOI17_simurgh)	C++17	30 / 100	453 ms	4628 KB

simurgh

#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 was[N * N];
int w[N][N];
int f[N];
vi g[N];
pii dfs(int node) {
	for (auto it : g[node])
		if (f[it] == -1 && !was[w[node][it]]) {
			f[it] = node;
			auto cnt = dfs(it);
			if (cnt != mp(-1,-1))
				return cnt;
		}
		else
		if (f[node] != it && f[it] != -1 && !was[w[node][it]])
			return mp(node,it);
	return mp(-1,-1);
}
int p[N];
int Ws[N * N];
int get(int k) {
	return k == p[k] ? k : p[k] = get(p[k]);
} 
vi find_roads(int n,vi u,vi v) {
	int m = u.size();
	for (int i = 0;i < m;++i)
		w[u[i]][v[i]] = w[v[i]][u[i]] = i,g[u[i]].pb(v[i]),g[v[i]].pb(u[i]);
	vi answer;
	for (int i = 0;i < n;++i)
		p[i] = i;
	vi ee;
	for (int i = 0;i < m;++i)
		if (get(u[i]) != get(v[i])) {
			ee.pb(i);
			p[get(u[i])] = get(v[i]);
		}
	do {
		vi cycle;
		for (int i = 0;i < n;++i)
			f[i] = -1;
		f[0] = 0;
		auto cnt = dfs(0);
		if (cnt != mp(-1,-1)) {
			cycle.pb(w[cnt.fi][cnt.se]);
			for (int i = cnt.fi;i != cnt.se;i = f[i])
				cycle.pb(w[i][f[i]]);
		} else {
			break;
		}
		for (auto it : cycle)
			was[it] = 1;
		vi rs;
		for (int i = 0;i < cycle.size();++i) {
			for (int j = 0;j < n;++j)
				p[j] = j;
			vi e;
			for (int j = 0;j < cycle.size();++j)
				if (i != j) {
					p[get(u[cycle[j]])] = get(v[cycle[j]]);
					e.pb(cycle[j]);
				}
			for (auto it : ee)
				if (get(u[it]) != get(v[it])) {
					e.pb(it);
					p[get(u[it])] = get(v[it]);
				}
			rs.pb(count_common_roads(e));
		}
		int mn = *min_element(all(rs));
		int mx = *max_element(all(rs));
		if (mn != mx) {
			for (int i = 0;i < cycle.size();++i)
				if (rs[i] == mn)
					Ws[cycle[i]] = 1,was[cycle[i]] = 0;
		}
	} while (1);
	for (int i = 0;i < m;++i)
		if (Ws[i] || (!Ws[i] && !was[i]))
			answer.pb(i);
	return answer;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0;i < cycle.size();++i) {
                  ~~^~~~~~~~~~~~~~
simurgh.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0;j < cycle.size();++j)
                   ~~^~~~~~~~~~~~~~
simurgh.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0;i < cycle.size();++i)
                   ~~^~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	3 ms	524 KB	correct
3	Correct	2 ms	524 KB	correct
4	Correct	3 ms	528 KB	correct
5	Correct	2 ms	528 KB	correct
6	Correct	2 ms	640 KB	correct
7	Correct	2 ms	640 KB	correct
8	Correct	2 ms	640 KB	correct
9	Correct	2 ms	640 KB	correct
10	Correct	4 ms	640 KB	correct
11	Correct	3 ms	640 KB	correct
12	Correct	3 ms	640 KB	correct
13	Correct	2 ms	640 KB	correct
14	Correct	15 ms	792 KB	correct
15	Correct	10 ms	792 KB	correct
16	Correct	13 ms	852 KB	correct
17	Correct	12 ms	852 KB	correct
18	Correct	5 ms	852 KB	correct
19	Correct	14 ms	980 KB	correct
20	Correct	10 ms	980 KB	correct
21	Correct	9 ms	980 KB	correct
22	Correct	11 ms	980 KB	correct
23	Correct	11 ms	980 KB	correct
24	Correct	14 ms	980 KB	correct
25	Correct	3 ms	980 KB	correct
26	Correct	11 ms	980 KB	correct
27	Correct	12 ms	980 KB	correct
28	Correct	7 ms	980 KB	correct
29	Correct	3 ms	980 KB	correct
30	Correct	12 ms	980 KB	correct
31	Correct	11 ms	980 KB	correct
32	Correct	15 ms	980 KB	correct
33	Correct	10 ms	1004 KB	correct
34	Incorrect	453 ms	2732 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2732 KB	correct
2	Correct	2 ms	2732 KB	correct
3	Incorrect	370 ms	4628 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	3 ms	524 KB	correct
3	Correct	2 ms	524 KB	correct
4	Correct	3 ms	528 KB	correct
5	Correct	2 ms	528 KB	correct
6	Correct	2 ms	640 KB	correct
7	Correct	2 ms	640 KB	correct
8	Correct	2 ms	640 KB	correct
9	Correct	2 ms	640 KB	correct
10	Correct	4 ms	640 KB	correct
11	Correct	3 ms	640 KB	correct
12	Correct	3 ms	640 KB	correct
13	Correct	2 ms	640 KB	correct
14	Correct	15 ms	792 KB	correct
15	Correct	10 ms	792 KB	correct
16	Correct	13 ms	852 KB	correct
17	Correct	12 ms	852 KB	correct
18	Correct	5 ms	852 KB	correct
19	Correct	14 ms	980 KB	correct
20	Correct	10 ms	980 KB	correct
21	Correct	9 ms	980 KB	correct
22	Correct	11 ms	980 KB	correct
23	Correct	11 ms	980 KB	correct
24	Correct	14 ms	980 KB	correct
25	Correct	3 ms	980 KB	correct
26	Correct	11 ms	980 KB	correct
27	Correct	12 ms	980 KB	correct
28	Correct	7 ms	980 KB	correct
29	Correct	3 ms	980 KB	correct
30	Correct	12 ms	980 KB	correct
31	Correct	11 ms	980 KB	correct
32	Correct	15 ms	980 KB	correct
33	Correct	10 ms	1004 KB	correct
34	Incorrect	453 ms	2732 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

답안 #58701

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0