oj.uz

답안 #336680

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
336680 2020-12-16T11:48:12 Z cheeheng 기지국 (IOI20_stations) C++14
52.3205 / 100
 976 ms 1260 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> AdjList[1005];
int dist[1005];
int subtreeSize[1005];

int cnt = 0;
void dfs(int i, int k){
    if(dist[i] != -1){return;}
    dist[i] = cnt;
    cnt ++;
    //printf("dist[%d]=%d\n", i, dist[i]);
    subtreeSize[i] = 1;
    for(int v: AdjList[i]){
        if(dist[v] == -1){
            dfs(v, k);
            subtreeSize[i] += subtreeSize[v];
        }
    }
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	cnt = 0;

	for(int i = 0; i < n; i ++){
        AdjList[i].clear();
	}

	int s = -1;
	memset(dist, -1, sizeof(dist));

	for(int i = 0; i < n-1; i ++){
        AdjList[u[i]].push_back(v[i]);
        AdjList[v[i]].push_back(u[i]);
	}

	/*
	for(int i = 0; i < n; i ++){
        if(AdjList[i].size() > 2){
            s = i;
            break;
        }
	}

	if(s == -1){
        for(int i = 0; i < n; i ++){
            if(AdjList[i].size() == 1){
                s = i;
                break;
            }
        }
	}

	dist[s] = 0;
	int cnt = 0;
	for(int v: AdjList[s]){
        dfs(v, cnt+1);
        cnt ++;
	}*/

	dfs(0, 0);

	for (int i = 0; i < n; i++) {
		labels[i] = dist[i]*1001 + subtreeSize[i];
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    //printf("s=%d t=%d c[0]=%d\n", s, t, c[0]);
    //sort(c.begin(), c.end());

    if(s < 1001){
        int indx = upper_bound(c.begin(), c.end(), t)-c.begin();
        assert(indx != 0);
        return c[indx-1];
    }

    if(s < t){
        // check if one is a parent of the other
        if( t/1001 >= (s/1001) + (s%1001) ){
            // s is not a parent of t
            //printf("Here\n");
            return c[0];
        }else{
            // s is a parent of t
            //printf("here\n");
            int indx = upper_bound(c.begin(), c.end(), t)-c.begin();
            assert(indx != 0);
            return c[indx-1];
        }
    }else{
        if( s/1001 >= (t/1001) + (t%1001) ){
            // s is not a parent of t
            //printf("Here\n");
            return c[0];
        }else{
            // s is a parent of t
            int indx = upper_bound(c.begin(), c.end(), s)-c.begin();
            assert(indx != 0);
            return c[indx-1];
        }
    }

    if(s/1000 == t/1000){
        // if one is a parent of the other
        if(s < t){
            return s+1;
        }else{
            return s-1;
        }
    }else{
        if(s%1000 == 1){
            return 0;
        }else{
            return s-1;
        }
    }

    /*int pow10[10];
    pow10[0] = 1;
    for(int i = 1; i < 10; i ++){
        pow10[i] = 10*pow10[i-1];
    }

    assert(s != t);

    for(int i = 1; i < 10; i ++){
        if(s == (t/pow10[i])){
            return t/pow10[i-1];
        }
    }

	return s/10;*/

    /*if(s == 0){
        return t/1000*1000+1;
    }

    if(s/1000 == t/1000){
        if(s < t){
            return s+1;
        }else{
            return s-1;
        }
    }else{
        if(s%1000 == 1){
            return 0;
        }else{
            return s-1;
        }
    }*/

    /*for(int i = 1; i < 11; i ++){
        if(s == (t>>i)){
            return (t>>(i-1));
        }
    }

	return s>>1;*/
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:32:6: warning: unused variable 's' [-Wunused-variable]
   32 |  int s = -1;
      |      ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 492 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=6010
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=0, k=1000, vertex=1, label=1512
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 553 ms 864 KB Output is correct
2 Correct 458 ms 1068 KB Output is correct
3 Correct 858 ms 864 KB Output is correct
4 Correct 643 ms 992 KB Output is correct
5 Correct 581 ms 736 KB Output is correct
6 Correct 453 ms 992 KB Output is correct
7 Correct 420 ms 864 KB Output is correct
8 Correct 3 ms 952 KB Output is correct
9 Correct 4 ms 776 KB Output is correct
10 Correct 1 ms 864 KB Output is correct
11 Correct 574 ms 1236 KB Output is correct
12 Correct 453 ms 1260 KB Output is correct
13 Correct 460 ms 1248 KB Output is correct
14 Correct 434 ms 896 KB Output is correct
15 Correct 58 ms 736 KB Output is correct
16 Correct 64 ms 904 KB Output is correct
17 Correct 108 ms 736 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 854 ms 816 KB Output is correct
2 Correct 646 ms 944 KB Output is correct
3 Correct 550 ms 864 KB Output is correct
4 Correct 3 ms 952 KB Output is correct
5 Correct 4 ms 864 KB Output is correct
6 Correct 1 ms 864 KB Output is correct
7 Correct 590 ms 864 KB Output is correct
8 Correct 859 ms 1080 KB Output is correct
9 Correct 700 ms 944 KB Output is correct
10 Correct 597 ms 944 KB Output is correct
11 Correct 5 ms 864 KB Output is correct
12 Correct 6 ms 864 KB Output is correct
13 Correct 5 ms 864 KB Output is correct
14 Correct 4 ms 864 KB Output is correct
15 Correct 2 ms 904 KB Output is correct
16 Correct 484 ms 864 KB Output is correct
17 Correct 559 ms 736 KB Output is correct
18 Correct 521 ms 992 KB Output is correct
19 Correct 524 ms 944 KB Output is correct
20 Correct 471 ms 1108 KB Output is correct

Subtask #5
26.3205 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 531 ms 992 KB Partially correct
2 Partially correct 424 ms 1032 KB Partially correct
3 Partially correct 948 ms 864 KB Partially correct
4 Partially correct 719 ms 736 KB Partially correct
5 Partially correct 683 ms 736 KB Partially correct
6 Partially correct 469 ms 1072 KB Partially correct
7 Partially correct 469 ms 992 KB Partially correct
8 Partially correct 3 ms 944 KB Partially correct
9 Partially correct 4 ms 864 KB Partially correct
10 Partially correct 2 ms 736 KB Partially correct
11 Partially correct 565 ms 736 KB Partially correct
12 Partially correct 515 ms 888 KB Partially correct
13 Partially correct 976 ms 736 KB Partially correct
14 Partially correct 737 ms 1108 KB Partially correct
15 Partially correct 542 ms 944 KB Partially correct
16 Partially correct 470 ms 864 KB Partially correct
17 Partially correct 547 ms 944 KB Partially correct
18 Partially correct 585 ms 1120 KB Partially correct
19 Partially correct 466 ms 1200 KB Partially correct
20 Partially correct 441 ms 896 KB Partially correct
21 Partially correct 66 ms 936 KB Partially correct
22 Partially correct 74 ms 1040 KB Partially correct
23 Partially correct 127 ms 880 KB Partially correct
24 Partially correct 7 ms 736 KB Partially correct
25 Partially correct 8 ms 776 KB Partially correct
26 Partially correct 5 ms 736 KB Partially correct
27 Partially correct 5 ms 736 KB Partially correct
28 Partially correct 2 ms 944 KB Partially correct
29 Partially correct 632 ms 1072 KB Partially correct
30 Partially correct 635 ms 964 KB Partially correct
31 Partially correct 603 ms 1108 KB Partially correct
32 Partially correct 567 ms 992 KB Partially correct
33 Partially correct 627 ms 952 KB Partially correct
34 Partially correct 351 ms 1084 KB Partially correct
35 Partially correct 477 ms 1060 KB Partially correct
36 Partially correct 530 ms 1240 KB Partially correct
37 Partially correct 611 ms 1120 KB Partially correct
38 Partially correct 444 ms 864 KB Partially correct
39 Partially correct 423 ms 1216 KB Partially correct
40 Partially correct 503 ms 1132 KB Partially correct
41 Partially correct 508 ms 1136 KB Partially correct
42 Partially correct 60 ms 736 KB Partially correct
43 Partially correct 113 ms 736 KB Partially correct
44 Partially correct 138 ms 736 KB Partially correct
45 Partially correct 200 ms 1116 KB Partially correct
46 Partially correct 380 ms 888 KB Partially correct
47 Partially correct 339 ms 1112 KB Partially correct
48 Partially correct 64 ms 1088 KB Partially correct
49 Partially correct 62 ms 864 KB Partially correct