답안 #64444 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64444	2018-08-04T13:35:06 Z	IvanC	Simurgh (IOI17_simurgh)	C++17	30 / 100	266 ms	4532 KB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

const int MAXN = 501;

int adjMatrix[MAXN][MAXN],dsu_parent[MAXN],N;
int e1[MAXN*MAXN],e2[MAXN*MAXN];
vi arestas_certas,arestas_dsu;

int dsu_find(int x){
	if(x == dsu_parent[x]) return x;
	return dsu_parent[x] = dsu_find(dsu_parent[x]);
}

void dsu_join(int x,int y){
	x = dsu_find(x);
	y = dsu_find(y);
	if(x == y) return;
	if(x > y) swap(x,y);
	dsu_parent[y] = x;
}

void dsu_reset(){
	for(int i = 0;i<N;i++) dsu_parent[i] = i;
}

void processa(int x){

	dsu_reset();
	arestas_dsu.clear();

	for(int i = 0;i<N;i++){
		if(i == x) continue;
		for(int j = 0;j<N;j++){
			if(j == x || adjMatrix[i][j] == -1) continue;
			if(dsu_find(i) != dsu_find(j)){
				dsu_join(i,j);
				arestas_dsu.push_back(adjMatrix[i][j]);
			}
		}
	}

	vector<vi> arestas_faltam;
	vi qual_pos;

	for(int i = 0;i<N;i++){
		if(i == x || dsu_find(i) != i) continue;
		vi novo_cjt;
		for(int j = 0;j<N;j++){
			if(j == x || adjMatrix[x][j] == -1) continue;
			if(dsu_find(j) == dsu_find(i)) novo_cjt.push_back(adjMatrix[x][j]);
		}
		qual_pos.push_back(arestas_dsu.size());
		arestas_dsu.push_back(novo_cjt[0]);
		arestas_faltam.push_back(novo_cjt);
	}

	for(int i = 0;i<arestas_faltam.size();i++){

		int maxv = 0;
		vi resultados;

		for(int j = 0;j<arestas_faltam[i].size();j++){
			arestas_dsu[qual_pos[i]] = arestas_faltam[i][j];
			resultados.push_back(count_common_roads(arestas_dsu));
			maxv = max(maxv,resultados.back());
		}

		for(int j = 0;j<arestas_faltam[i].size();j++){
			if(resultados[j] == maxv) arestas_certas.push_back(arestas_faltam[i][j]);
		}

	}

}

vi find_roads(int n, vi u, vi v) {

	memset(adjMatrix,-1,sizeof(adjMatrix));
	N = n;

	for(int i = 0;i<u.size();i++){
		adjMatrix[u[i]][v[i]] = i;
		adjMatrix[v[i]][u[i]] = i;
		e1[i] = u[i];
		e2[i] = v[i];
	}

	for(int i = 0;i<n;i++) processa(i);

	sort(arestas_certas.begin(),arestas_certas.end());
	arestas_certas.erase(unique(arestas_certas.begin(),arestas_certas.end()),arestas_certas.end());

	return arestas_certas;

}

Compilation message

simurgh.cpp: In function 'void processa(int)':
simurgh.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<arestas_faltam.size();i++){
                ~^~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0;j<arestas_faltam[i].size();j++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:72:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0;j<arestas_faltam[i].size();j++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<u.size();i++){
                ~^~~~~~~~~

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1272 KB	correct
2	Correct	4 ms	1512 KB	correct
3	Correct	4 ms	1608 KB	correct
4	Correct	4 ms	1608 KB	correct
5	Correct	4 ms	1608 KB	correct
6	Correct	4 ms	1608 KB	correct
7	Correct	3 ms	1660 KB	correct
8	Correct	4 ms	1660 KB	correct
9	Correct	3 ms	1660 KB	correct
10	Correct	4 ms	1732 KB	correct
11	Correct	3 ms	1732 KB	correct
12	Correct	5 ms	1732 KB	correct
13	Correct	5 ms	1732 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1272 KB	correct
2	Correct	4 ms	1512 KB	correct
3	Correct	4 ms	1608 KB	correct
4	Correct	4 ms	1608 KB	correct
5	Correct	4 ms	1608 KB	correct
6	Correct	4 ms	1608 KB	correct
7	Correct	3 ms	1660 KB	correct
8	Correct	4 ms	1660 KB	correct
9	Correct	3 ms	1660 KB	correct
10	Correct	4 ms	1732 KB	correct
11	Correct	3 ms	1732 KB	correct
12	Correct	5 ms	1732 KB	correct
13	Correct	5 ms	1732 KB	correct
14	Correct	10 ms	1792 KB	correct
15	Correct	8 ms	1800 KB	correct
16	Correct	8 ms	1824 KB	correct
17	Correct	8 ms	1848 KB	correct
18	Correct	6 ms	1848 KB	correct
19	Correct	7 ms	1900 KB	correct
20	Correct	7 ms	1900 KB	correct
21	Correct	8 ms	1900 KB	correct
22	Correct	7 ms	1900 KB	correct
23	Correct	6 ms	1900 KB	correct
24	Correct	7 ms	1900 KB	correct
25	Correct	6 ms	1900 KB	correct
26	Correct	6 ms	1900 KB	correct
27	Correct	8 ms	1900 KB	correct
28	Correct	7 ms	1944 KB	correct
29	Correct	5 ms	1944 KB	correct
30	Correct	8 ms	1944 KB	correct
31	Correct	8 ms	1944 KB	correct
32	Correct	7 ms	1944 KB	correct
33	Correct	8 ms	1944 KB	correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1272 KB	correct
2	Correct	4 ms	1512 KB	correct
3	Correct	4 ms	1608 KB	correct
4	Correct	4 ms	1608 KB	correct
5	Correct	4 ms	1608 KB	correct
6	Correct	4 ms	1608 KB	correct
7	Correct	3 ms	1660 KB	correct
8	Correct	4 ms	1660 KB	correct
9	Correct	3 ms	1660 KB	correct
10	Correct	4 ms	1732 KB	correct
11	Correct	3 ms	1732 KB	correct
12	Correct	5 ms	1732 KB	correct
13	Correct	5 ms	1732 KB	correct
14	Correct	10 ms	1792 KB	correct
15	Correct	8 ms	1800 KB	correct
16	Correct	8 ms	1824 KB	correct
17	Correct	8 ms	1848 KB	correct
18	Correct	6 ms	1848 KB	correct
19	Correct	7 ms	1900 KB	correct
20	Correct	7 ms	1900 KB	correct
21	Correct	8 ms	1900 KB	correct
22	Correct	7 ms	1900 KB	correct
23	Correct	6 ms	1900 KB	correct
24	Correct	7 ms	1900 KB	correct
25	Correct	6 ms	1900 KB	correct
26	Correct	6 ms	1900 KB	correct
27	Correct	8 ms	1900 KB	correct
28	Correct	7 ms	1944 KB	correct
29	Correct	5 ms	1944 KB	correct
30	Correct	8 ms	1944 KB	correct
31	Correct	8 ms	1944 KB	correct
32	Correct	7 ms	1944 KB	correct
33	Correct	8 ms	1944 KB	correct
34	Incorrect	266 ms	2824 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1272 KB	correct
2	Correct	4 ms	1512 KB	correct
3	Correct	4 ms	1608 KB	correct
4	Correct	4 ms	1608 KB	correct
5	Correct	4 ms	1608 KB	correct
6	Correct	4 ms	1608 KB	correct
7	Correct	3 ms	1660 KB	correct
8	Correct	4 ms	1660 KB	correct
9	Correct	3 ms	1660 KB	correct
10	Correct	4 ms	1732 KB	correct
11	Correct	3 ms	1732 KB	correct
12	Correct	5 ms	1732 KB	correct
13	Correct	5 ms	1732 KB	correct
14	Correct	10 ms	1792 KB	correct
15	Correct	8 ms	1800 KB	correct
16	Correct	8 ms	1824 KB	correct
17	Correct	8 ms	1848 KB	correct
18	Correct	6 ms	1848 KB	correct
19	Correct	7 ms	1900 KB	correct
20	Correct	7 ms	1900 KB	correct
21	Correct	8 ms	1900 KB	correct
22	Correct	7 ms	1900 KB	correct
23	Correct	6 ms	1900 KB	correct
24	Correct	7 ms	1900 KB	correct
25	Correct	6 ms	1900 KB	correct
26	Correct	6 ms	1900 KB	correct
27	Correct	8 ms	1900 KB	correct
28	Correct	7 ms	1944 KB	correct
29	Correct	5 ms	1944 KB	correct
30	Correct	8 ms	1944 KB	correct
31	Correct	8 ms	1944 KB	correct
32	Correct	7 ms	1944 KB	correct
33	Correct	8 ms	1944 KB	correct
34	Incorrect	266 ms	2824 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

답안 #64444

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