oj.uz

답안 #397934

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397934 2021-05-03T12:00:32 Z cfalas 기지국 (IOI20_stations) C++14
76 / 100
 1154 ms 788 KB 
#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)

vector<vi> adj;
vi labels;
int cnt=0;
vi sub;
int d=0;
void dfs(int s, int p=-1){
	d++;
	//cout<<"enter "<<s<<" "<<cnt<<endl;
	labels[s] = cnt++;
	for(auto v : adj[s]) if(v!=p) dfs(v, s), sub[s]+=sub[v];
	d--;
	//cout<<"leave "<<s<<" "<<cnt<<endl;
	if(d%2==1) labels[s] = cnt;
	cnt++;

}

vi label(int n, int k, std::vector<int> u, std::vector<int> v) {
	cnt = 0;
	adj.assign(n, vi());
	sub.assign(n, 1);
	labels.assign(n, 0);
	FOR(i,n-1){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs(0);
	//FOR(i,n) cout<<labels[i]<<" "<<sub[i]-1<<endl;

	//FOA(v, labels) cout<<v<<" "; cout<<endl;

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	sort(c.begin(), c.end());
	if(s<c[0]){
		// s is t_in
		// c is t_out
		//cout<<s<<" "<<t<<endl;
		int prev = s;
		FOA(v,c){
			if(prev<t && t<=v) return v;
			prev = v;
		}
		return c.back();
	}
	else{
		// s is t_out
		// c is t_in
		//cout<<s<<" "<<t<<endl;
		reverse(c.begin(), c.end());
		//cout<<"N: "; FOA(v,c) cout<<v<<" ";
		//cout<<endl;
		int prev = s;
		FOA(v,c){
			if(v<=t && t<prev) return v;
			prev = v;
		}
		return c.back();
	}
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 676 ms 704 KB Output is correct
2 Correct 577 ms 636 KB Output is correct
3 Correct 1000 ms 400 KB Output is correct
4 Correct 761 ms 488 KB Output is correct
5 Correct 808 ms 488 KB Output is correct
6 Correct 518 ms 604 KB Output is correct
7 Correct 554 ms 556 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 4 ms 472 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Correct 681 ms 496 KB Output is correct
12 Correct 546 ms 612 KB Output is correct
13 Correct 570 ms 696 KB Output is correct
14 Correct 587 ms 528 KB Output is correct
15 Correct 52 ms 452 KB Output is correct
16 Correct 90 ms 548 KB Output is correct
17 Correct 136 ms 528 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 972 ms 400 KB Output is correct
2 Correct 865 ms 496 KB Output is correct
3 Correct 769 ms 528 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 7 ms 472 KB Output is correct
6 Correct 2 ms 480 KB Output is correct
7 Correct 670 ms 492 KB Output is correct
8 Correct 1154 ms 492 KB Output is correct
9 Correct 898 ms 400 KB Output is correct
10 Correct 737 ms 516 KB Output is correct
11 Correct 5 ms 472 KB Output is correct
12 Correct 7 ms 472 KB Output is correct
13 Correct 5 ms 480 KB Output is correct
14 Correct 5 ms 472 KB Output is correct
15 Correct 2 ms 480 KB Output is correct
16 Correct 722 ms 496 KB Output is correct
17 Correct 579 ms 404 KB Output is correct
18 Correct 682 ms 492 KB Output is correct
19 Correct 613 ms 504 KB Output is correct
20 Correct 576 ms 420 KB Output is correct

Subtask #5
50.0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 581 ms 648 KB Partially correct
2 Partially correct 452 ms 620 KB Partially correct
3 Correct 1022 ms 400 KB Output is correct
4 Correct 967 ms 532 KB Output is correct
5 Correct 715 ms 400 KB Output is correct
6 Partially correct 546 ms 616 KB Partially correct
7 Partially correct 634 ms 528 KB Partially correct
8 Correct 2 ms 480 KB Output is correct
9 Correct 4 ms 452 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Partially correct 587 ms 604 KB Partially correct
12 Partially correct 526 ms 528 KB Partially correct
13 Correct 1019 ms 520 KB Output is correct
14 Correct 817 ms 400 KB Output is correct
15 Correct 556 ms 492 KB Output is correct
16 Partially correct 492 ms 528 KB Partially correct
17 Correct 734 ms 492 KB Output is correct
18 Partially correct 485 ms 716 KB Partially correct
19 Partially correct 496 ms 688 KB Partially correct
20 Partially correct 445 ms 520 KB Partially correct
21 Correct 57 ms 420 KB Output is correct
22 Partially correct 94 ms 540 KB Partially correct
23 Partially correct 153 ms 528 KB Partially correct
24 Correct 7 ms 468 KB Output is correct
25 Correct 5 ms 472 KB Output is correct
26 Correct 5 ms 472 KB Output is correct
27 Correct 4 ms 472 KB Output is correct
28 Correct 2 ms 480 KB Output is correct
29 Correct 706 ms 496 KB Output is correct
30 Correct 722 ms 488 KB Output is correct
31 Correct 609 ms 488 KB Output is correct
32 Correct 508 ms 400 KB Output is correct
33 Correct 579 ms 400 KB Output is correct
34 Partially correct 384 ms 620 KB Partially correct
35 Partially correct 556 ms 684 KB Partially correct
36 Partially correct 576 ms 696 KB Partially correct
37 Partially correct 557 ms 604 KB Partially correct
38 Partially correct 598 ms 684 KB Partially correct
39 Partially correct 576 ms 676 KB Partially correct
40 Partially correct 522 ms 608 KB Partially correct
41 Partially correct 449 ms 700 KB Partially correct
42 Partially correct 62 ms 528 KB Partially correct
43 Partially correct 124 ms 708 KB Partially correct
44 Partially correct 123 ms 528 KB Partially correct
45 Partially correct 176 ms 528 KB Partially correct
46 Partially correct 390 ms 528 KB Partially correct
47 Partially correct 408 ms 528 KB Partially correct
48 Partially correct 65 ms 528 KB Partially correct
49 Partially correct 72 ms 788 KB Partially correct