답안 #33836 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
33836	2017-11-03T00:03:42 Z	mohammad_kilani	Simurgh (IOI17_simurgh)	C++14	30 / 100	106 ms	5508 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 comp[N];


void DFS(int node,int cant,int cur,vector<int> &v){
	vis[node] = vi;
	comp[node] = cur;
	for(int i=0;i<g[node].size();i++){
		if(g[node][i].first != cant && vis[g[node][i].first] != vi){
			v.push_back(g[node][i].second);
			DFS(g[node][i].first,cant,cur,v);
		}
	}
}

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));
	}
	for(int i=0;i<n;i++){
		vi++;
		int cnt = 0 ;
		vector<int> tree, tree2 ; 
		for(int j=0;j<n;j++){
			if(j == i) continue;
			if(vis[j] != vi){
				DFS(j,i,cnt++,tree2);
			}
		}
		vector< pair<int,int> > v , v2;
		for(int j=0;j<g[i].size();j++){
			v.push_back(make_pair(comp[g[i][j].first],g[i][j].second));
		}
		sort(v.begin(),v.end());
		int res = -1;
		for(int k=0;k<v.size();k++){
			if(k == 0 || v[k].first != v[k-1].first){
				for(int j=0;j<v2.size();j++){
					if(v2[j].first == res){
						ok[v2[j].second] = true;
					}
				}
				res = -1;
				v2.clear();
				bool taken[N] = {0};
				tree.clear();
				for(int j=0;j<g[i].size();j++){
					if(!taken[comp[g[i][j].first]] && comp[g[i][j].first] != v[k].first){
						taken[comp[g[i][j].first]] = true;
						tree.push_back(g[i][j].second);
					}
				}
				for(int i=0;i<tree2.size();i++) tree.push_back(tree2[i]);
			}
			if(asked[v[k].second]) continue;
			//asked[v[i].second] = true;
			tree.push_back(v[k].second);
			int cur = count_common_roads(tree);
			tree.pop_back();
			v2.push_back(make_pair(cur,v[k].second));
			res = max(res,cur);

		}
		for(int j=0;j<v2.size();j++){
			if(v2[j].first == res){
				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 DFS(int, int, int, std::vector<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 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++){
               ^
simurgh.cpp:39:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[i].size();j++){
                ^
simurgh.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0;k<v.size();k++){
                ^
simurgh.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<v2.size();j++){
                  ^
simurgh.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<g[i].size();j++){
                  ^
simurgh.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tree2.size();i++) tree.push_back(tree2[i]);
                  ^
simurgh.cpp:72:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v2.size();j++){
                ^
simurgh.cpp:78: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	2544 KB	correct
15	Correct	3 ms	2544 KB	correct
16	Correct	0 ms	2544 KB	correct
17	Correct	0 ms	2544 KB	correct
18	Correct	0 ms	2544 KB	correct
19	Correct	0 ms	2544 KB	correct
20	Correct	0 ms	2544 KB	correct
21	Correct	0 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
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	2544 KB	correct
15	Correct	3 ms	2544 KB	correct
16	Correct	0 ms	2544 KB	correct
17	Correct	0 ms	2544 KB	correct
18	Correct	0 ms	2544 KB	correct
19	Correct	0 ms	2544 KB	correct
20	Correct	0 ms	2544 KB	correct
21	Correct	0 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	Incorrect	106 ms	3488 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2544 KB	correct
2	Correct	0 ms	2544 KB	correct
3	Incorrect	89 ms	5508 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	2544 KB	correct
15	Correct	3 ms	2544 KB	correct
16	Correct	0 ms	2544 KB	correct
17	Correct	0 ms	2544 KB	correct
18	Correct	0 ms	2544 KB	correct
19	Correct	0 ms	2544 KB	correct
20	Correct	0 ms	2544 KB	correct
21	Correct	0 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	Incorrect	106 ms	3488 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

답안 #33836

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