답안 #431999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431999	2021-06-17T18:46:12 Z	gonengazit	기지국 (IOI20_stations)	C++14	73.3618 / 100	864 ms	792 KB

stations

#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define x first
#define y second
vector<int> labels;
vector<vector<int>> g;
int tme;
void dfs1(int i,int f=0,int t=0){
	int tin=++tme;
	for(auto u:g[i]){
		if(u!=f){
			dfs1(u,i,(t+1)%2);
		}
	}
	int tout=++tme;
	if(t==0){
		labels[i]=tin*2;
	}
	else{
		labels[i]=tout*2+1;
	}
}

// void dfs1(int i, int f=0){
// 	int tin=++tme;
// 	for(auto u:g[i]){
// 		if(u!=f){
// 			dfs1(u,i);
// 		}
// 	}
// 	int tout=tme;
// 	labels[i]=tin*1000+tout;
// }
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	tme=-1;
	labels.assign(n,-1);
	g.assign(n,vector<int>());
	for(int i=0; i<n-1; i++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}

	dfs1(0);
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	
	int r=s%2;
	s/=2;
	vector<pair<ii,int>> cld;
	int f=-1;
	if(r==0){
		int prev=s;
		for(auto i:c){
			int k=i/2;
			cld.emplace_back(ii(prev+1,k),i);
			prev=k;
		}
		if(s!=0){
			f=cld.back().y;
			cld.pop_back();
		}
	}
	else{
		f=c[0];
		for(int j=1; j<c.size(); j++){
			int i=c[j];
			int k=i/2;
			if(!cld.empty())
				cld.back().x.y=k-1;
			cld.emplace_back(ii(k,-1),i);
		}
		if(!cld.empty()){
			cld.back().x.y=s;
		}
	}

	t/=2;

	for(auto i:cld){
		if(i.x.x<=t&&i.x.y>=t){
			return i.y;
		}
	}
	return f;
}
/*
1
5 100
0 1
1 2
1 3
2 4
3
0 1 2
1 2 2
1 4 2*/

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int j=1; j<c.size(); j++){
      |                ~^~~~~~~~~

Subtask #1

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	412 KB	Invalid labels (values out of range). scenario=2, k=1000, vertex=1, label=3981
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	6 ms	360 KB	Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=2045
2	Halted	0 ms	0 KB	-

Subtask #3

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	543 ms	652 KB	Output is correct
2	Correct	456 ms	604 KB	Output is correct
3	Correct	849 ms	520 KB	Output is correct
4	Correct	648 ms	400 KB	Output is correct
5	Correct	575 ms	400 KB	Output is correct
6	Correct	431 ms	608 KB	Output is correct
7	Correct	460 ms	616 KB	Output is correct
8	Correct	3 ms	468 KB	Output is correct
9	Correct	3 ms	468 KB	Output is correct
10	Correct	1 ms	476 KB	Output is correct
11	Correct	580 ms	520 KB	Output is correct
12	Correct	458 ms	776 KB	Output is correct
13	Correct	503 ms	620 KB	Output is correct
14	Correct	497 ms	516 KB	Output is correct
15	Correct	55 ms	400 KB	Output is correct
16	Correct	59 ms	544 KB	Output is correct
17	Correct	106 ms	528 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	849 ms	476 KB	Output is correct
2	Correct	654 ms	400 KB	Output is correct
3	Correct	560 ms	488 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	4 ms	468 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	555 ms	400 KB	Output is correct
8	Correct	864 ms	400 KB	Output is correct
9	Correct	625 ms	492 KB	Output is correct
10	Correct	555 ms	400 KB	Output is correct
11	Correct	5 ms	468 KB	Output is correct
12	Correct	6 ms	468 KB	Output is correct
13	Correct	4 ms	476 KB	Output is correct
14	Correct	4 ms	468 KB	Output is correct
15	Correct	2 ms	476 KB	Output is correct
16	Correct	499 ms	400 KB	Output is correct
17	Correct	505 ms	400 KB	Output is correct
18	Correct	501 ms	620 KB	Output is correct
19	Correct	477 ms	400 KB	Output is correct
20	Correct	486 ms	528 KB	Output is correct

Subtask #5

47.3618 / 61.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	507 ms	772 KB	Partially correct
2	Partially correct	413 ms	608 KB	Partially correct
3	Correct	835 ms	400 KB	Output is correct
4	Correct	719 ms	400 KB	Output is correct
5	Correct	649 ms	400 KB	Output is correct
6	Partially correct	440 ms	612 KB	Partially correct
7	Partially correct	433 ms	484 KB	Partially correct
8	Correct	3 ms	496 KB	Output is correct
9	Correct	5 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Partially correct	431 ms	520 KB	Partially correct
12	Partially correct	524 ms	480 KB	Partially correct
13	Correct	827 ms	400 KB	Output is correct
14	Correct	657 ms	400 KB	Output is correct
15	Correct	613 ms	484 KB	Output is correct
16	Partially correct	437 ms	480 KB	Partially correct
17	Correct	562 ms	400 KB	Output is correct
18	Partially correct	475 ms	704 KB	Partially correct
19	Partially correct	445 ms	596 KB	Partially correct
20	Partially correct	410 ms	496 KB	Partially correct
21	Correct	62 ms	468 KB	Output is correct
22	Partially correct	67 ms	488 KB	Partially correct
23	Partially correct	92 ms	656 KB	Partially correct
24	Correct	5 ms	468 KB	Output is correct
25	Correct	5 ms	468 KB	Output is correct
26	Correct	5 ms	468 KB	Output is correct
27	Correct	4 ms	476 KB	Output is correct
28	Correct	2 ms	480 KB	Output is correct
29	Correct	524 ms	400 KB	Output is correct
30	Correct	515 ms	532 KB	Output is correct
31	Correct	483 ms	400 KB	Output is correct
32	Correct	508 ms	488 KB	Output is correct
33	Correct	511 ms	400 KB	Output is correct
34	Partially correct	296 ms	656 KB	Partially correct
35	Partially correct	408 ms	728 KB	Partially correct
36	Partially correct	453 ms	744 KB	Partially correct
37	Partially correct	451 ms	608 KB	Partially correct
38	Partially correct	443 ms	608 KB	Partially correct
39	Partially correct	460 ms	708 KB	Partially correct
40	Partially correct	439 ms	708 KB	Partially correct
41	Partially correct	456 ms	616 KB	Partially correct
42	Partially correct	66 ms	544 KB	Partially correct
43	Partially correct	104 ms	488 KB	Partially correct
44	Partially correct	139 ms	792 KB	Partially correct
45	Partially correct	178 ms	532 KB	Partially correct
46	Partially correct	295 ms	568 KB	Partially correct
47	Partially correct	310 ms	484 KB	Partially correct
48	Partially correct	67 ms	620 KB	Partially correct
49	Partially correct	57 ms	660 KB	Partially correct