oj.uz

답안 #397883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397883 2021-05-03T10:44:41 Z cfalas 기지국 (IOI20_stations) C++14
10 / 100
 1220 ms 784 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;
void dfs(int s, int p=-1){
	labels[s] = cnt++;
	for(auto v : adj[s]) if(v!=p) dfs(v, s), sub[s]+=sub[v];
}

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]<<endl;
	FOR(i,n) labels[i] = labels[i]*1000 + sub[i];

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

	return labels;
}

int get_s(int x){ return x % 1000; }

int find_next_station(int s, int t, std::vector<int> c) {
	//cout<<s<<" "<<t<<endl;
	int lt = t/1000;
	int ls = s/1000;

	int prev = ls;
	sort(c.begin(), c.end());
	FOA(x, c){
		if((x/1000)<ls) continue;
		int xs = get_s(x);
		if(prev<lt && lt<=prev+xs) return x;
		prev+=xs;
	}
	//cout<<s<<" "<<get_s(s)<<endl;
	return *min_element(c.begin(), c.end());

}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 659 ms 656 KB Output is correct
2 Correct 503 ms 656 KB Output is correct
3 Correct 1220 ms 476 KB Output is correct
4 Correct 654 ms 400 KB Output is correct
5 Correct 582 ms 528 KB Output is correct
6 Correct 570 ms 628 KB Output is correct
7 Correct 497 ms 620 KB Output is correct
8 Correct 2 ms 432 KB Output is correct
9 Correct 4 ms 476 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Correct 740 ms 492 KB Output is correct
12 Correct 535 ms 696 KB Output is correct
13 Correct 501 ms 656 KB Output is correct
14 Correct 566 ms 528 KB Output is correct
15 Correct 62 ms 452 KB Output is correct
16 Correct 67 ms 548 KB Output is correct
17 Incorrect 144 ms 548 KB Wrong query response.

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1022 ms 488 KB Output is correct
2 Correct 740 ms 492 KB Output is correct
3 Correct 635 ms 400 KB Output is correct
4 Correct 3 ms 472 KB Output is correct
5 Correct 5 ms 480 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 713 ms 400 KB Output is correct
8 Correct 1039 ms 400 KB Output is correct
9 Correct 906 ms 492 KB Output is correct
10 Correct 687 ms 536 KB Output is correct
11 Correct 6 ms 480 KB Output is correct
12 Correct 5 ms 484 KB Output is correct
13 Correct 5 ms 484 KB Output is correct
14 Correct 5 ms 472 KB Output is correct
15 Correct 2 ms 480 KB Output is correct
16 Correct 587 ms 528 KB Output is correct
17 Correct 578 ms 400 KB Output is correct
18 Correct 617 ms 528 KB Output is correct
19 Correct 568 ms 400 KB Output is correct
20 Correct 656 ms 492 KB Output is correct

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 639 ms 680 KB Partially correct
2 Partially correct 536 ms 656 KB Partially correct
3 Partially correct 1212 ms 400 KB Partially correct
4 Partially correct 671 ms 400 KB Partially correct
5 Partially correct 775 ms 520 KB Partially correct
6 Partially correct 540 ms 528 KB Partially correct
7 Partially correct 618 ms 784 KB Partially correct
8 Partially correct 3 ms 472 KB Partially correct
9 Partially correct 4 ms 484 KB Partially correct
10 Partially correct 2 ms 484 KB Partially correct
11 Partially correct 429 ms 528 KB Partially correct
12 Partially correct 558 ms 656 KB Partially correct
13 Partially correct 1117 ms 404 KB Partially correct
14 Partially correct 731 ms 528 KB Partially correct
15 Partially correct 814 ms 400 KB Partially correct
16 Partially correct 523 ms 528 KB Partially correct
17 Partially correct 755 ms 400 KB Partially correct
18 Partially correct 507 ms 608 KB Partially correct
19 Partially correct 638 ms 748 KB Partially correct
20 Partially correct 512 ms 488 KB Partially correct
21 Partially correct 77 ms 420 KB Partially correct
22 Partially correct 67 ms 528 KB Partially correct
23 Incorrect 107 ms 528 KB Wrong query response.
24 Halted 0 ms 0 KB -