답안 #165346

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
165346	2019-11-26T12:48:46 Z	Segtree	Simurgh (IOI17_simurgh)	C++14	30 / 100	276 ms	3652 KB

simurgh

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include"simurgh.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 250



vector<P> g[N];
unordered_set<int> vis;
vector<int> edges;
int blg[N];
void dfs(ll x,ll eid,ll root){
    if(vis.find(x)!=vis.end())return;
    vis.insert(x);
    if(-1!=eid)edges.push_back(eid);
    blg[x]=root;
    for(auto y:g[x]){
	dfs(y.first,y.second,root);
    }
}
vector<int> find_roads(int n,vector<int> u,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));
    }
    vector<int> ans;
    for(int i=0;i<n;i++){
	edges.clear();
	vis.clear();
	vis.insert(i);
	for(int j=0;j<n;j++){
	    dfs(j,-1,j);
	}
	unordered_map<ll,vector<int> >mas;
	for(auto e:g[i]){
	    mas[blg[e.first]].push_back(e.second);
	}
	for(auto v:mas){
	    for(auto vv:mas){
		if(v!=vv)edges.push_back(vv.second[0]);
	    }
	    int ma=-1;
	    unordered_map<int,int> sav;
	    for(auto e:v.second){
		edges.push_back(e);
		//if(edges.size()<n-1)cout<<1/0<<endl;
		sav[e]=count_common_roads(edges);
		chmax(ma,sav[e]);
		edges.pop_back();
	    }
	    for(auto e:v.second){
		if(sav[e]==ma&&u[e]==i)ans.push_back(e);
	    }
	    for(auto vv:mas){
		if(v!=vv)edges.pop_back();
	    }
	}
    }
    if(ans.size()!=n-1)cout<<1/0<<endl;
    return ans;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<u.size();i++){
                 ~^~~~~~~~~
simurgh.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ans.size()!=n-1)cout<<1/0<<endl;
        ~~~~~~~~~~^~~~~
simurgh.cpp:66:31: warning: division by zero [-Wdiv-by-zero]
     if(ans.size()!=n-1)cout<<1/0<<endl;
                              ~^~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	correct
2	Correct	2 ms	256 KB	correct
3	Runtime error	23 ms	3652 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

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

답안 #165346

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