oj.uz

Submission #336671

# Submission time Handle Problem Language Result Execution time Memory
336671 2020-12-16T10:29:33 Z cheeheng Stations (IOI20_stations) C++14
10 / 100
 899 ms 1120 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;
    int cnt = 1;
    for(int v: AdjList[i]){
        if(dist[v] == -1){
            dfs(v, 10*k+cnt);
            cnt ++;
        }
    }
}

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, 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);

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 948 KB Output is correct
2 Correct 679 ms 820 KB Output is correct
3 Correct 609 ms 948 KB Output is correct
4 Correct 3 ms 948 KB Output is correct
5 Correct 4 ms 1120 KB Output is correct
6 Correct 1 ms 736 KB Output is correct
7 Correct 626 ms 864 KB Output is correct
8 Correct 892 ms 1108 KB Output is correct
9 Correct 664 ms 900 KB Output is correct
10 Correct 571 ms 864 KB Output is correct
11 Correct 7 ms 948 KB Output is correct
12 Correct 5 ms 956 KB Output is correct
13 Correct 4 ms 948 KB Output is correct
14 Correct 4 ms 864 KB Output is correct
15 Correct 1 ms 948 KB Output is correct
16 Correct 515 ms 864 KB Output is correct
17 Correct 536 ms 864 KB Output is correct
18 Correct 470 ms 864 KB Output is correct
19 Correct 557 ms 948 KB Output is correct
20 Correct 571 ms 864 KB Output is correct

Subtask #5
0 / 61.0

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