oj.uz

답안 #408486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
408486 2021-05-19T07:44:24 Z muhammad_hokimiyon 기지국 (IOI20_stations) C++14
76 / 100
 1784 ms 55780 KB 
#include "stations.h"
#include <vector>
#include<bits/stdc++.h>

#define fi first
#define se second

using namespace std;

const int N = 1e3 + 7;

vector<int> tin,tout,lv;

void dfs(vector<vector<int>> g, int x, int p, int &G)
{
    tin[x] = G++;
    for(auto y : g[x]){
        if(y == p)continue;
        lv[y] = 1 - lv[x];
        dfs(g, y, x, G);
    }
    tout[x] = G++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	vector<vector<int>> g(n + 7);
	tin.resize(n + 7);
	tout.resize(n + 7);
	lv.resize(n + 7);
	for(int i = 0; i < n - 1; i++){
        int x = u[i], y = v[i];
        g[x].push_back(y);
        g[y].push_back(x);
	}
	int st = 0;
	dfs(g, 0, 0, st);
	for(int i = 0; i < n; i++){
        if(lv[i])labels[i] = tin[i];
        else labels[i] = tout[i];
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    if(s < c[0]){
        vector<pair<int, int>> nc;
        int ls = s;
        for(int i = 0; i + 1 < (int)c.size(); i++){
            nc.push_back({ls, c[i]});
            ls = c[i] + 1;
        }
        for(auto x : nc){
            if(x.fi <= t && t <= x.se){
                return x.se;
            }
        }
        return c.back();
    }else{
        assert(s > c.back());
        vector<pair<int, int>> nc;
        int ls = s - 1;
        for(int i = (int)c.size() - 1; i > 0; i--){
            nc.push_back({c[i], ls});
            ls = c[i] - 1;
        }
        for(auto x : nc){
            if(x.fi <= t && t <= x.se){
                return x.fi;
            }
        }
        return c[0];
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1081 ms 55620 KB Output is correct
2 Correct 1323 ms 53204 KB Output is correct
3 Correct 1188 ms 400 KB Output is correct
4 Correct 847 ms 400 KB Output is correct
5 Correct 885 ms 528 KB Output is correct
6 Correct 1250 ms 53612 KB Output is correct
7 Correct 746 ms 42720 KB Output is correct
8 Correct 3 ms 400 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 829 ms 400 KB Output is correct
12 Correct 1174 ms 54588 KB Output is correct
13 Correct 1387 ms 50308 KB Output is correct
14 Correct 643 ms 3144 KB Output is correct
15 Correct 76 ms 504 KB Output is correct
16 Correct 239 ms 668 KB Output is correct
17 Correct 697 ms 740 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1625 ms 400 KB Output is correct
2 Correct 728 ms 468 KB Output is correct
3 Correct 730 ms 512 KB Output is correct
4 Correct 5 ms 592 KB Output is correct
5 Correct 7 ms 400 KB Output is correct
6 Correct 3 ms 540 KB Output is correct
7 Correct 817 ms 536 KB Output is correct
8 Correct 1111 ms 400 KB Output is correct
9 Correct 1281 ms 520 KB Output is correct
10 Correct 933 ms 400 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 6 ms 468 KB Output is correct
13 Correct 7 ms 468 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Correct 3 ms 652 KB Output is correct
16 Correct 687 ms 400 KB Output is correct
17 Correct 647 ms 400 KB Output is correct
18 Correct 605 ms 400 KB Output is correct
19 Correct 898 ms 484 KB Output is correct
20 Correct 1018 ms 424 KB Output is correct

Subtask #5
50.0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1180 ms 55668 KB Partially correct
2 Partially correct 1238 ms 48904 KB Partially correct
3 Correct 1510 ms 464 KB Output is correct
4 Correct 720 ms 404 KB Output is correct
5 Correct 801 ms 400 KB Output is correct
6 Partially correct 1652 ms 55628 KB Partially correct
7 Partially correct 887 ms 31364 KB Partially correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 7 ms 472 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Partially correct 1418 ms 1192 KB Partially correct
12 Partially correct 1014 ms 1136 KB Partially correct
13 Correct 1117 ms 468 KB Output is correct
14 Correct 1125 ms 464 KB Output is correct
15 Correct 855 ms 484 KB Output is correct
16 Partially correct 708 ms 1176 KB Partially correct
17 Correct 673 ms 400 KB Output is correct
18 Partially correct 1287 ms 37508 KB Partially correct
19 Partially correct 1283 ms 51672 KB Partially correct
20 Partially correct 641 ms 4184 KB Partially correct
21 Correct 88 ms 452 KB Output is correct
22 Partially correct 300 ms 588 KB Partially correct
23 Partially correct 870 ms 744 KB Partially correct
24 Correct 5 ms 468 KB Output is correct
25 Correct 5 ms 420 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 6 ms 468 KB Output is correct
28 Correct 2 ms 480 KB Output is correct
29 Correct 653 ms 400 KB Output is correct
30 Correct 738 ms 484 KB Output is correct
31 Correct 734 ms 484 KB Output is correct
32 Correct 665 ms 660 KB Output is correct
33 Correct 622 ms 400 KB Output is correct
34 Partially correct 1027 ms 42232 KB Partially correct
35 Partially correct 1525 ms 55780 KB Partially correct
36 Partially correct 1347 ms 46020 KB Partially correct
37 Partially correct 1301 ms 13592 KB Partially correct
38 Partially correct 1283 ms 13640 KB Partially correct
39 Partially correct 1331 ms 18044 KB Partially correct
40 Partially correct 1347 ms 17780 KB Partially correct
41 Partially correct 1784 ms 14588 KB Partially correct
42 Partially correct 459 ms 688 KB Partially correct
43 Partially correct 661 ms 740 KB Partially correct
44 Partially correct 636 ms 1056 KB Partially correct
45 Partially correct 860 ms 1588 KB Partially correct
46 Partially correct 974 ms 13824 KB Partially correct
47 Partially correct 1293 ms 26944 KB Partially correct
48 Partially correct 544 ms 1092 KB Partially correct
49 Partially correct 684 ms 1420 KB Partially correct