oj.uz

답안 #349976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349976 2021-01-18T19:13:32 Z evn 기지국 (IOI20_stations) C++14
69.868 / 100
 1095 ms 1248 KB 
#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
typedef long long ll;
typedef pair<int, int> pii;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int timer = 0;
int depth[1005];
int in[1005];
int out[1005];
vector<int> adj[1005];
void dfs(int u, int p){
	if(depth[u] % 2 == 0)in[u] = timer++;
	for(int v : adj[u]){
		if(v != p){
			depth[v] = depth[u]+1;
			dfs(v, u);
		}
	}
	if(depth[u] % 2 == 1)out[u] = timer++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	for(int i = 0; i < n;i ++){
		adj[i].clear();
		depth[i] = 0;
	}
	for(int i = 0; i < u.size(); i++){
		int a, b;
		a = u[i];
		b = v[i];
		adj[a].pb(b);
		adj[b].pb(a);
	}
	dfs(0, -1);
	for (int i = 0; i < n; i++) {
		if(depth[i] % 2 == 0)labels[i] = in[i];
		else{labels[i] = out[i];}
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	if(c.size() == 1)return c[0];
	if(c[0] > s){
		//this is the in value
		if(t < s || t >= c[c.size()-1])return c[c.size()-1];
		for(int i = 0;i < c.size()-1; i++){
			if(t <= c[i])return c[i];
		}
	}
	else{
		//this is the out value
		if(t <= c[0] || t > s)return c[0];
		for(int i = c.size()-1; i >= 1; i--){
			if(t >= c[i])return c[i];
		}
	}
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int i = 0;i < c.size()-1; i++){
      |                 ~~^~~~~~~~~~~~
stations.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
   67 | }
      | ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 537 ms 864 KB Output is correct
2 Correct 443 ms 864 KB Output is correct
3 Correct 849 ms 948 KB Output is correct
4 Correct 736 ms 864 KB Output is correct
5 Correct 587 ms 864 KB Output is correct
6 Correct 458 ms 1084 KB Output is correct
7 Correct 436 ms 992 KB Output is correct
8 Correct 3 ms 988 KB Output is correct
9 Correct 3 ms 736 KB Output is correct
10 Correct 1 ms 736 KB Output is correct
11 Correct 603 ms 940 KB Output is correct
12 Correct 412 ms 1208 KB Output is correct
13 Correct 455 ms 1084 KB Output is correct
14 Correct 509 ms 892 KB Output is correct
15 Correct 66 ms 980 KB Output is correct
16 Correct 81 ms 904 KB Output is correct
17 Correct 136 ms 1032 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 914 ms 864 KB Output is correct
2 Correct 948 ms 940 KB Output is correct
3 Correct 711 ms 864 KB Output is correct
4 Correct 4 ms 1076 KB Output is correct
5 Correct 5 ms 940 KB Output is correct
6 Correct 1 ms 736 KB Output is correct
7 Correct 722 ms 992 KB Output is correct
8 Correct 1095 ms 864 KB Output is correct
9 Correct 675 ms 940 KB Output is correct
10 Correct 775 ms 864 KB Output is correct
11 Correct 6 ms 988 KB Output is correct
12 Correct 5 ms 736 KB Output is correct
13 Correct 5 ms 864 KB Output is correct
14 Correct 4 ms 948 KB Output is correct
15 Correct 2 ms 736 KB Output is correct
16 Correct 499 ms 736 KB Output is correct
17 Correct 650 ms 1116 KB Output is correct
18 Correct 527 ms 864 KB Output is correct
19 Correct 520 ms 940 KB Output is correct
20 Correct 519 ms 948 KB Output is correct

Subtask #5
43.868 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 494 ms 1084 KB Partially correct
2 Partially correct 438 ms 1248 KB Partially correct
3 Correct 917 ms 824 KB Output is correct
4 Correct 775 ms 864 KB Output is correct
5 Correct 624 ms 864 KB Output is correct
6 Partially correct 440 ms 992 KB Partially correct
7 Correct 426 ms 864 KB Output is correct
8 Correct 3 ms 864 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 2 ms 948 KB Output is correct
11 Partially correct 475 ms 876 KB Partially correct
12 Partially correct 596 ms 1024 KB Partially correct
13 Correct 1057 ms 1068 KB Output is correct
14 Correct 750 ms 948 KB Output is correct
15 Correct 617 ms 948 KB Output is correct
16 Correct 485 ms 892 KB Output is correct
17 Correct 638 ms 940 KB Output is correct
18 Partially correct 490 ms 1104 KB Partially correct
19 Partially correct 487 ms 1212 KB Partially correct
20 Correct 482 ms 864 KB Output is correct
21 Correct 72 ms 980 KB Output is correct
22 Partially correct 73 ms 864 KB Partially correct
23 Partially correct 123 ms 864 KB Partially correct
24 Correct 6 ms 736 KB Output is correct
25 Correct 5 ms 736 KB Output is correct
26 Correct 6 ms 864 KB Output is correct
27 Correct 5 ms 736 KB Output is correct
28 Correct 2 ms 940 KB Output is correct
29 Correct 612 ms 736 KB Output is correct
30 Correct 497 ms 940 KB Output is correct
31 Correct 537 ms 940 KB Output is correct
32 Correct 522 ms 992 KB Output is correct
33 Correct 470 ms 940 KB Output is correct
34 Partially correct 312 ms 864 KB Partially correct
35 Partially correct 421 ms 864 KB Partially correct
36 Partially correct 449 ms 992 KB Partially correct
37 Partially correct 438 ms 992 KB Partially correct
38 Partially correct 535 ms 864 KB Partially correct
39 Partially correct 609 ms 1088 KB Partially correct
40 Partially correct 461 ms 1008 KB Partially correct
41 Partially correct 489 ms 896 KB Partially correct
42 Partially correct 69 ms 864 KB Partially correct
43 Partially correct 140 ms 988 KB Partially correct
44 Partially correct 148 ms 1008 KB Partially correct
45 Partially correct 158 ms 992 KB Partially correct
46 Partially correct 353 ms 736 KB Partially correct
47 Partially correct 302 ms 1004 KB Partially correct
48 Partially correct 63 ms 1208 KB Partially correct
49 Partially correct 65 ms 992 KB Partially correct