답안 #58784 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58784	2018-07-19T11:04:27 Z	reality	Simurgh (IOI17_simurgh)	C++17	51 / 100	547 ms	8008 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 called = 0;
	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 {
			int ok = 1;
			for (int i = 0;i < m;++i)
				if (Ws[i])
					ok &= !was[i];
			if (ok)
				break;
			else {
				for (int i = 0;i < m;++i)
					if (Ws[i])
						was[i] = 0;
			}
		}
		for (auto it : cycle)
			was[it] = 1;
		vector < pii > rs;
		int shit = 0;
		for (int i = 0;i < cycle.size();++i) {
				if (Ws[cycle[i]]) {
					++shit;
					if (shit > 1)
						continue;
				}
				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(mp(count_common_roads(e),cycle[i]));
			}
		int mn = min_element(all(rs))->fi;
		int mx = max_element(all(rs))->fi;
		for (auto it : rs)
			if (Ws[it.se])
				assert(it.fi == mn);
		if (mn != mx) {
			for (auto it : rs)
				if (it.fi == mn)
					Ws[it.se] = 1;
		}
	} 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:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0;i < cycle.size();++i) {
                  ~~^~~~~~~~~~~~~~
simurgh.cpp:90:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0;j < cycle.size();++j)
                    ~~^~~~~~~~~~~~~~
simurgh.cpp:41:6: warning: unused variable 'called' [-Wunused-variable]
  int called = 0;
      ^~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	3 ms	376 KB	correct
3	Correct	2 ms	536 KB	correct
4	Correct	2 ms	536 KB	correct
5	Correct	2 ms	536 KB	correct
6	Correct	2 ms	536 KB	correct
7	Correct	3 ms	544 KB	correct
8	Correct	2 ms	552 KB	correct
9	Correct	2 ms	688 KB	correct
10	Correct	2 ms	688 KB	correct
11	Correct	3 ms	688 KB	correct
12	Correct	2 ms	688 KB	correct
13	Correct	2 ms	688 KB	correct
14	Correct	7 ms	944 KB	correct
15	Correct	7 ms	944 KB	correct
16	Correct	7 ms	944 KB	correct
17	Correct	6 ms	948 KB	correct
18	Correct	4 ms	956 KB	correct
19	Correct	8 ms	960 KB	correct
20	Correct	8 ms	968 KB	correct
21	Correct	8 ms	1008 KB	correct
22	Correct	6 ms	1008 KB	correct
23	Correct	5 ms	1008 KB	correct
24	Correct	4 ms	1008 KB	correct
25	Correct	3 ms	1008 KB	correct
26	Correct	6 ms	1008 KB	correct
27	Correct	5 ms	1012 KB	correct
28	Correct	4 ms	1016 KB	correct
29	Correct	4 ms	1016 KB	correct
30	Correct	5 ms	1016 KB	correct
31	Correct	6 ms	1028 KB	correct
32	Correct	5 ms	1032 KB	correct
33	Correct	7 ms	1036 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	3 ms	376 KB	correct
3	Correct	2 ms	536 KB	correct
4	Correct	2 ms	536 KB	correct
5	Correct	2 ms	536 KB	correct
6	Correct	2 ms	536 KB	correct
7	Correct	3 ms	544 KB	correct
8	Correct	2 ms	552 KB	correct
9	Correct	2 ms	688 KB	correct
10	Correct	2 ms	688 KB	correct
11	Correct	3 ms	688 KB	correct
12	Correct	2 ms	688 KB	correct
13	Correct	2 ms	688 KB	correct
14	Correct	7 ms	944 KB	correct
15	Correct	7 ms	944 KB	correct
16	Correct	7 ms	944 KB	correct
17	Correct	6 ms	948 KB	correct
18	Correct	4 ms	956 KB	correct
19	Correct	8 ms	960 KB	correct
20	Correct	8 ms	968 KB	correct
21	Correct	8 ms	1008 KB	correct
22	Correct	6 ms	1008 KB	correct
23	Correct	5 ms	1008 KB	correct
24	Correct	4 ms	1008 KB	correct
25	Correct	3 ms	1008 KB	correct
26	Correct	6 ms	1008 KB	correct
27	Correct	5 ms	1012 KB	correct
28	Correct	4 ms	1016 KB	correct
29	Correct	4 ms	1016 KB	correct
30	Correct	5 ms	1016 KB	correct
31	Correct	6 ms	1028 KB	correct
32	Correct	5 ms	1032 KB	correct
33	Correct	7 ms	1036 KB	correct
34	Correct	456 ms	2880 KB	correct
35	Correct	547 ms	3152 KB	correct
36	Correct	318 ms	3152 KB	correct
37	Correct	23 ms	3152 KB	correct
38	Correct	479 ms	3612 KB	correct
39	Correct	414 ms	3612 KB	correct
40	Correct	308 ms	3612 KB	correct
41	Correct	498 ms	4004 KB	correct
42	Correct	516 ms	4220 KB	correct
43	Correct	214 ms	4220 KB	correct
44	Correct	177 ms	4220 KB	correct
45	Correct	205 ms	4220 KB	correct
46	Correct	166 ms	4220 KB	correct
47	Correct	59 ms	4220 KB	correct
48	Correct	7 ms	4220 KB	correct
49	Correct	18 ms	4220 KB	correct
50	Correct	55 ms	4220 KB	correct
51	Correct	231 ms	4220 KB	correct
52	Correct	205 ms	4220 KB	correct
53	Correct	142 ms	4284 KB	correct
54	Correct	226 ms	4640 KB	correct
55	Correct	195 ms	4800 KB	correct
56	Correct	190 ms	4800 KB	correct
57	Correct	204 ms	4800 KB	correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4800 KB	correct
2	Correct	3 ms	4800 KB	correct
3	Incorrect	374 ms	8008 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	376 KB	correct
3	Correct	2 ms	536 KB	correct
4	Correct	2 ms	536 KB	correct
5	Correct	2 ms	536 KB	correct
6	Correct	2 ms	536 KB	correct
7	Correct	3 ms	544 KB	correct
8	Correct	2 ms	552 KB	correct
9	Correct	2 ms	688 KB	correct
10	Correct	2 ms	688 KB	correct
11	Correct	3 ms	688 KB	correct
12	Correct	2 ms	688 KB	correct
13	Correct	2 ms	688 KB	correct
14	Correct	7 ms	944 KB	correct
15	Correct	7 ms	944 KB	correct
16	Correct	7 ms	944 KB	correct
17	Correct	6 ms	948 KB	correct
18	Correct	4 ms	956 KB	correct
19	Correct	8 ms	960 KB	correct
20	Correct	8 ms	968 KB	correct
21	Correct	8 ms	1008 KB	correct
22	Correct	6 ms	1008 KB	correct
23	Correct	5 ms	1008 KB	correct
24	Correct	4 ms	1008 KB	correct
25	Correct	3 ms	1008 KB	correct
26	Correct	6 ms	1008 KB	correct
27	Correct	5 ms	1012 KB	correct
28	Correct	4 ms	1016 KB	correct
29	Correct	4 ms	1016 KB	correct
30	Correct	5 ms	1016 KB	correct
31	Correct	6 ms	1028 KB	correct
32	Correct	5 ms	1032 KB	correct
33	Correct	7 ms	1036 KB	correct
34	Correct	456 ms	2880 KB	correct
35	Correct	547 ms	3152 KB	correct
36	Correct	318 ms	3152 KB	correct
37	Correct	23 ms	3152 KB	correct
38	Correct	479 ms	3612 KB	correct
39	Correct	414 ms	3612 KB	correct
40	Correct	308 ms	3612 KB	correct
41	Correct	498 ms	4004 KB	correct
42	Correct	516 ms	4220 KB	correct
43	Correct	214 ms	4220 KB	correct
44	Correct	177 ms	4220 KB	correct
45	Correct	205 ms	4220 KB	correct
46	Correct	166 ms	4220 KB	correct
47	Correct	59 ms	4220 KB	correct
48	Correct	7 ms	4220 KB	correct
49	Correct	18 ms	4220 KB	correct
50	Correct	55 ms	4220 KB	correct
51	Correct	231 ms	4220 KB	correct
52	Correct	205 ms	4220 KB	correct
53	Correct	142 ms	4284 KB	correct
54	Correct	226 ms	4640 KB	correct
55	Correct	195 ms	4800 KB	correct
56	Correct	190 ms	4800 KB	correct
57	Correct	204 ms	4800 KB	correct
58	Correct	3 ms	4800 KB	correct
59	Correct	3 ms	4800 KB	correct
60	Incorrect	374 ms	8008 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #58784

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.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
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0