제출 #336680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336680		cheeheng	기지국 (IOI20_stations)	C++14	52.32 / 100	976 ms	1260 KiB

stations

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

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 26.3205 / 61