답안 #58700 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58700	2018-07-18T23:10:41 Z	reality	Simurgh (IOI17_simurgh)	C++17	30 / 100	540 ms	4560 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 = 512;
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	2 ms	488 KB	correct
3	Correct	3 ms	544 KB	correct
4	Correct	2 ms	544 KB	correct
5	Correct	2 ms	544 KB	correct
6	Correct	3 ms	572 KB	correct
7	Correct	2 ms	596 KB	correct
8	Correct	2 ms	608 KB	correct
9	Correct	3 ms	612 KB	correct
10	Correct	2 ms	616 KB	correct
11	Correct	2 ms	620 KB	correct
12	Correct	2 ms	624 KB	correct
13	Correct	2 ms	644 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	488 KB	correct
3	Correct	3 ms	544 KB	correct
4	Correct	2 ms	544 KB	correct
5	Correct	2 ms	544 KB	correct
6	Correct	3 ms	572 KB	correct
7	Correct	2 ms	596 KB	correct
8	Correct	2 ms	608 KB	correct
9	Correct	3 ms	612 KB	correct
10	Correct	2 ms	616 KB	correct
11	Correct	2 ms	620 KB	correct
12	Correct	2 ms	624 KB	correct
13	Correct	2 ms	644 KB	correct
14	Correct	13 ms	796 KB	correct
15	Correct	12 ms	796 KB	correct
16	Correct	12 ms	800 KB	correct
17	Correct	10 ms	824 KB	correct
18	Correct	7 ms	836 KB	correct
19	Correct	17 ms	948 KB	correct
20	Correct	9 ms	948 KB	correct
21	Correct	11 ms	980 KB	correct
22	Correct	15 ms	980 KB	correct
23	Correct	15 ms	996 KB	correct
24	Correct	10 ms	996 KB	correct
25	Correct	2 ms	996 KB	correct
26	Correct	10 ms	996 KB	correct
27	Correct	11 ms	996 KB	correct
28	Correct	5 ms	996 KB	correct
29	Correct	3 ms	996 KB	correct
30	Correct	11 ms	996 KB	correct
31	Correct	11 ms	996 KB	correct
32	Correct	13 ms	996 KB	correct
33	Correct	11 ms	996 KB	correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	488 KB	correct
3	Correct	3 ms	544 KB	correct
4	Correct	2 ms	544 KB	correct
5	Correct	2 ms	544 KB	correct
6	Correct	3 ms	572 KB	correct
7	Correct	2 ms	596 KB	correct
8	Correct	2 ms	608 KB	correct
9	Correct	3 ms	612 KB	correct
10	Correct	2 ms	616 KB	correct
11	Correct	2 ms	620 KB	correct
12	Correct	2 ms	624 KB	correct
13	Correct	2 ms	644 KB	correct
14	Correct	13 ms	796 KB	correct
15	Correct	12 ms	796 KB	correct
16	Correct	12 ms	800 KB	correct
17	Correct	10 ms	824 KB	correct
18	Correct	7 ms	836 KB	correct
19	Correct	17 ms	948 KB	correct
20	Correct	9 ms	948 KB	correct
21	Correct	11 ms	980 KB	correct
22	Correct	15 ms	980 KB	correct
23	Correct	15 ms	996 KB	correct
24	Correct	10 ms	996 KB	correct
25	Correct	2 ms	996 KB	correct
26	Correct	10 ms	996 KB	correct
27	Correct	11 ms	996 KB	correct
28	Correct	5 ms	996 KB	correct
29	Correct	3 ms	996 KB	correct
30	Correct	11 ms	996 KB	correct
31	Correct	11 ms	996 KB	correct
32	Correct	13 ms	996 KB	correct
33	Correct	11 ms	996 KB	correct
34	Incorrect	540 ms	2596 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2596 KB	correct
2	Correct	3 ms	2596 KB	correct
3	Incorrect	398 ms	4560 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	2 ms	488 KB	correct
3	Correct	3 ms	544 KB	correct
4	Correct	2 ms	544 KB	correct
5	Correct	2 ms	544 KB	correct
6	Correct	3 ms	572 KB	correct
7	Correct	2 ms	596 KB	correct
8	Correct	2 ms	608 KB	correct
9	Correct	3 ms	612 KB	correct
10	Correct	2 ms	616 KB	correct
11	Correct	2 ms	620 KB	correct
12	Correct	2 ms	624 KB	correct
13	Correct	2 ms	644 KB	correct
14	Correct	13 ms	796 KB	correct
15	Correct	12 ms	796 KB	correct
16	Correct	12 ms	800 KB	correct
17	Correct	10 ms	824 KB	correct
18	Correct	7 ms	836 KB	correct
19	Correct	17 ms	948 KB	correct
20	Correct	9 ms	948 KB	correct
21	Correct	11 ms	980 KB	correct
22	Correct	15 ms	980 KB	correct
23	Correct	15 ms	996 KB	correct
24	Correct	10 ms	996 KB	correct
25	Correct	2 ms	996 KB	correct
26	Correct	10 ms	996 KB	correct
27	Correct	11 ms	996 KB	correct
28	Correct	5 ms	996 KB	correct
29	Correct	3 ms	996 KB	correct
30	Correct	11 ms	996 KB	correct
31	Correct	11 ms	996 KB	correct
32	Correct	13 ms	996 KB	correct
33	Correct	11 ms	996 KB	correct
34	Incorrect	540 ms	2596 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

답안 #58700

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