oj.uz

Submission #336675

# Submission time Handle Problem Language Result Execution time Memory
336675 2020-12-16T11:33:18 Z cheeheng Stations (IOI20_stations) C++14
0 / 100
 5 ms 1228 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]*1000 + 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 < 1000){
        int indx = lower_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/1000 >= (s/1000) + (s%1000) ){
            // s is not a parent of t
            //printf("Here\n");
            return c[0];
        }else{
            // s is a parent of t
            int indx = lower_bound(c.begin(), c.end(), t)-c.begin();
            assert(indx != 0);
            return c[indx-1];
        }
    }else{
        // t cannot be a parent of s
        return c[0];
    }

    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

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 528 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

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 368 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

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1228 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1200 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1120 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -