oj.uz

Submission #336670

# Submission time Handle Problem Language Result Execution time Memory
336670 2020-12-16T10:15:07 Z cheeheng Stations (IOI20_stations) C++14
21 / 100
 1037 ms 1084 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

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

void dfs(int i, int k){
    if(dist[i] != -1){return;}
    dist[i] = k;
    for(int v: AdjList[i]){
        if(dist[v] == -1){
            dfs(v, k+1);
            return;
        }
    }
}

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

	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, 1000*cnt+1);
        cnt ++;
	}

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

int find_next_station(int s, int t, std::vector<int> c) {
    //printf("s=%d t=%d\n", s, t);
    assert(s != t);

    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;*/
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 892 KB Output is correct
2 Correct 546 ms 888 KB Output is correct
3 Correct 923 ms 1024 KB Output is correct
4 Correct 743 ms 956 KB Output is correct
5 Correct 678 ms 948 KB Output is correct
6 Correct 515 ms 1020 KB Output is correct
7 Correct 463 ms 900 KB Output is correct
8 Correct 3 ms 864 KB Output is correct
9 Correct 4 ms 948 KB Output is correct
10 Correct 2 ms 736 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 364 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=3, label=1001
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 888 KB Output is correct
2 Correct 444 ms 888 KB Output is correct
3 Correct 831 ms 956 KB Output is correct
4 Correct 638 ms 864 KB Output is correct
5 Correct 568 ms 948 KB Output is correct
6 Correct 428 ms 864 KB Output is correct
7 Correct 406 ms 864 KB Output is correct
8 Correct 2 ms 988 KB Output is correct
9 Correct 4 ms 904 KB Output is correct
10 Correct 1 ms 948 KB Output is correct
11 Correct 578 ms 864 KB Output is correct
12 Correct 454 ms 1036 KB Output is correct
13 Correct 438 ms 1020 KB Output is correct
14 Correct 542 ms 900 KB Output is correct
15 Correct 72 ms 940 KB Output is correct
16 Correct 84 ms 736 KB Output is correct
17 Correct 109 ms 736 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 876 KB Output is correct
2 Correct 689 ms 948 KB Output is correct
3 Correct 703 ms 864 KB Output is correct
4 Correct 2 ms 864 KB Output is correct
5 Correct 6 ms 864 KB Output is correct
6 Correct 1 ms 736 KB Output is correct
7 Correct 648 ms 864 KB Output is correct
8 Correct 948 ms 1076 KB Output is correct
9 Correct 701 ms 1084 KB Output is correct
10 Correct 624 ms 1076 KB Output is correct
11 Incorrect 1 ms 364 KB Invalid labels (values out of range). scenario=5, k=1000000000, vertex=5, label=-1
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 864 KB Output is correct
2 Correct 484 ms 888 KB Output is correct
3 Correct 906 ms 948 KB Output is correct
4 Correct 799 ms 948 KB Output is correct
5 Correct 695 ms 948 KB Output is correct
6 Correct 500 ms 892 KB Output is correct
7 Correct 492 ms 900 KB Output is correct
8 Correct 3 ms 956 KB Output is correct
9 Correct 4 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Incorrect 4 ms 364 KB Invalid labels (values out of range). scenario=0, k=1000000000, vertex=6, label=-1
12 Halted 0 ms 0 KB -