답안 #33860 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
33860	2017-11-03T15:59:34 Z	mohammad_kilani	Simurgh (IOI17_simurgh)	C++14	51 / 100	199 ms	5772 KB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 501;
int  vis[N] , vi = 0;
vector< pair<int,int> > g[N], T[N];
vector< int >  ans;
bool ok[N * N] = {0} , asked[N * N];
int edge[N] , comp[N];


void gettree(int node,vector<int> &v,int prnt){
	vis[node] = vi;
	edge[node] = prnt;
	for(int i=0;i<g[node].size();i++){
		int newnode = g[node][i].first;
		if(vis[newnode] != vi){
			T[node].push_back(g[node][i]);
			T[newnode].push_back(make_pair(node,g[node][i].second));
			v.push_back(g[node][i].second);
			gettree(newnode,v,g[node][i].second);
		}
	}
}

void DFS(int node,int cant,int cur){
	vis[node] = vi;
	comp[node] = cur;
	for(int i=0;i<T[node].size();i++){
		int newnode = T[node][i].first;
		if(vis[newnode] != vi && newnode != cant){
			DFS(newnode,cant,cur);
		}
	}
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	for(int i=0;i<u.size();i++){
		g[u[i]].push_back(make_pair(v[i],i));
		g[v[i]].push_back(make_pair(u[i],i));
	}
	vi++;
	vector< int > tree;
	gettree(0,tree,-1);
	int res = count_common_roads(tree);
	for(int i=0;i<n;i++){
		if(edge[i] == -1) continue;
		int cnt = 0 ;
		vi++;
		DFS(u[edge[i]],v[edge[i]],0);
		DFS(v[edge[i]],u[edge[i]],1);
		int ask = 0 , ask2 = 0 , mx = res ;
		vector< pair<int,int> > v2;
		v2.push_back(make_pair(res,edge[i]));
		for(int j=0;j<u.size();j++){
			if(j == edge[i]) continue;
			if(comp[u[j]] == comp[v[j]]) continue;
			if(asked[j] && ask == 0){
				vector<int> r;
				for(int k=0;k<tree.size();k++){
					if(tree[k] != edge[i]){
						r.push_back(tree[k]);
					}
				}
				r.push_back(j);
				ask2 = count_common_roads(r);
				if(ok[j]) ask = 1; else ask = 2;
			}
			if(asked[j]) continue;
			vector<int> r;
			for(int k=0;k<tree.size();k++){
				if(tree[k] != edge[i]){
					r.push_back(tree[k]);
				}
			}
			r.push_back(j);
			int cur = count_common_roads(r);
			v2.push_back(make_pair(cur,j));
			mx = max(mx,cur);
		}
		if(ask == 0){
			for(int j=0;j<v2.size();j++){
				asked[v2[j].second] = true;
				if(v2[j].first == mx) ok[v2[j].second] = true;
			}
		}
		else if(ask == 1){
			for(int j=0;j<v2.size();j++){
				asked[v2[j].second] = true;
				if(v2[j].first == ask2) ok[v2[j].second] = true;
			}
		}
		else{
			for(int j=0;j<v2.size();j++){
				asked[v2[j].second] = true;
				if(v2[j].first != ask2) ok[v2[j].second] = true;
			}
		}
	}
	for(int i=0;i<u.size();i++) if(ok[i]) ans.push_back(i);
	return ans;
}

Compilation message

simurgh.cpp: In function 'void gettree(int, std::vector<int>&, int)':
simurgh.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
               ^
simurgh.cpp: In function 'void DFS(int, int, int)':
simurgh.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T[node].size();i++){
               ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++){
               ^
simurgh.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<u.size();j++){
                ^
simurgh.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<tree.size();k++){
                  ^
simurgh.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<tree.size();k++){
                 ^
simurgh.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<v2.size();j++){
                 ^
simurgh.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<v2.size();j++){
                 ^
simurgh.cpp:94:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<v2.size();j++){
                 ^
simurgh.cpp:48:7: warning: unused variable 'cnt' [-Wunused-variable]
   int cnt = 0 ;
       ^
simurgh.cpp:100:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++) if(ok[i]) ans.push_back(i);
               ^

Subtask #1
13.0 / 13.0

#	결과	메모리	Grader output
1	Correct	2544 KB	correct
2	Correct	2544 KB	correct
3	Correct	2544 KB	correct
4	Correct	2544 KB	correct
5	Correct	2544 KB	correct
6	Correct	2544 KB	correct
7	Correct	2544 KB	correct
8	Correct	2544 KB	correct
9	Correct	2544 KB	correct
10	Correct	2544 KB	correct
11	Correct	2544 KB	correct
12	Correct	2544 KB	correct
13	Correct	2544 KB	correct

Subtask #2
17.0 / 17.0

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

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2544 KB	correct
2	Correct	0 ms	2544 KB	correct
3	Correct	0 ms	2544 KB	correct
4	Correct	0 ms	2544 KB	correct
5	Correct	0 ms	2544 KB	correct
6	Correct	0 ms	2544 KB	correct
7	Correct	0 ms	2544 KB	correct
8	Correct	0 ms	2544 KB	correct
9	Correct	0 ms	2544 KB	correct
10	Correct	0 ms	2544 KB	correct
11	Correct	0 ms	2544 KB	correct
12	Correct	0 ms	2544 KB	correct
13	Correct	0 ms	2544 KB	correct
14	Correct	0 ms	2676 KB	correct
15	Correct	0 ms	2676 KB	correct
16	Correct	0 ms	2676 KB	correct
17	Correct	0 ms	2544 KB	correct
18	Correct	0 ms	2544 KB	correct
19	Correct	0 ms	2676 KB	correct
20	Correct	3 ms	2676 KB	correct
21	Correct	3 ms	2544 KB	correct
22	Correct	0 ms	2544 KB	correct
23	Correct	0 ms	2544 KB	correct
24	Correct	0 ms	2544 KB	correct
25	Correct	0 ms	2544 KB	correct
26	Correct	0 ms	2544 KB	correct
27	Correct	0 ms	2544 KB	correct
28	Correct	0 ms	2544 KB	correct
29	Correct	0 ms	2544 KB	correct
30	Correct	0 ms	2544 KB	correct
31	Correct	0 ms	2544 KB	correct
32	Correct	0 ms	2544 KB	correct
33	Correct	0 ms	2544 KB	correct
34	Correct	186 ms	3736 KB	correct
35	Correct	176 ms	3748 KB	correct
36	Correct	129 ms	3516 KB	correct
37	Correct	6 ms	2676 KB	correct
38	Correct	196 ms	3736 KB	correct
39	Correct	156 ms	3724 KB	correct
40	Correct	129 ms	3644 KB	correct
41	Correct	199 ms	3756 KB	correct
42	Correct	179 ms	3764 KB	correct
43	Correct	89 ms	3256 KB	correct
44	Correct	69 ms	3128 KB	correct
45	Correct	83 ms	3108 KB	correct
46	Correct	59 ms	2968 KB	correct
47	Correct	26 ms	2808 KB	correct
48	Correct	0 ms	2544 KB	correct
49	Correct	6 ms	2676 KB	correct
50	Correct	26 ms	2808 KB	correct
51	Correct	83 ms	3108 KB	correct
52	Correct	73 ms	3124 KB	correct
53	Correct	59 ms	2968 KB	correct
54	Correct	96 ms	3424 KB	correct
55	Correct	93 ms	3112 KB	correct
56	Correct	93 ms	3244 KB	correct
57	Correct	89 ms	3244 KB	correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2544 KB	correct
2	Correct	0 ms	2544 KB	correct
3	Correct	0 ms	2544 KB	correct
4	Correct	0 ms	2544 KB	correct
5	Correct	0 ms	2544 KB	correct
6	Correct	0 ms	2544 KB	correct
7	Correct	0 ms	2544 KB	correct
8	Correct	0 ms	2544 KB	correct
9	Correct	0 ms	2544 KB	correct
10	Correct	0 ms	2544 KB	correct
11	Correct	0 ms	2544 KB	correct
12	Correct	0 ms	2544 KB	correct
13	Correct	0 ms	2544 KB	correct
14	Correct	0 ms	2676 KB	correct
15	Correct	0 ms	2676 KB	correct
16	Correct	0 ms	2676 KB	correct
17	Correct	0 ms	2544 KB	correct
18	Correct	0 ms	2544 KB	correct
19	Correct	0 ms	2676 KB	correct
20	Correct	3 ms	2676 KB	correct
21	Correct	3 ms	2544 KB	correct
22	Correct	0 ms	2544 KB	correct
23	Correct	0 ms	2544 KB	correct
24	Correct	0 ms	2544 KB	correct
25	Correct	0 ms	2544 KB	correct
26	Correct	0 ms	2544 KB	correct
27	Correct	0 ms	2544 KB	correct
28	Correct	0 ms	2544 KB	correct
29	Correct	0 ms	2544 KB	correct
30	Correct	0 ms	2544 KB	correct
31	Correct	0 ms	2544 KB	correct
32	Correct	0 ms	2544 KB	correct
33	Correct	0 ms	2544 KB	correct
34	Correct	186 ms	3736 KB	correct
35	Correct	176 ms	3748 KB	correct
36	Correct	129 ms	3516 KB	correct
37	Correct	6 ms	2676 KB	correct
38	Correct	196 ms	3736 KB	correct
39	Correct	156 ms	3724 KB	correct
40	Correct	129 ms	3644 KB	correct
41	Correct	199 ms	3756 KB	correct
42	Correct	179 ms	3764 KB	correct
43	Correct	89 ms	3256 KB	correct
44	Correct	69 ms	3128 KB	correct
45	Correct	83 ms	3108 KB	correct
46	Correct	59 ms	2968 KB	correct
47	Correct	26 ms	2808 KB	correct
48	Correct	0 ms	2544 KB	correct
49	Correct	6 ms	2676 KB	correct
50	Correct	26 ms	2808 KB	correct
51	Correct	83 ms	3108 KB	correct
52	Correct	73 ms	3124 KB	correct
53	Correct	59 ms	2968 KB	correct
54	Correct	96 ms	3424 KB	correct
55	Correct	93 ms	3112 KB	correct
56	Correct	93 ms	3244 KB	correct
57	Correct	89 ms	3244 KB	correct
58	Correct	0 ms	2544 KB	correct
59	Correct	0 ms	2544 KB	correct
60	Incorrect	106 ms	5772 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #33860

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