oj.uz

답안 #366145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366145 2021-02-13T10:17:40 Z 79brue 기지국 (IOI20_stations) C++14
0 / 100
 1029 ms 1080 KB 
#include <bits/stdc++.h>
#include "stations.h"

using namespace std;

typedef long long ll;

vector<int> link[1002];
bool visited[1002];
int arr[1002];
int sz[1002];

void szd(int x, int par=-1){
    sz[x] = 1;
    for(auto y: link[x]){
        if(y == par) continue;
        szd(y, x);
        sz[x] += sz[y];
    }
}

void dfs(int x, int l, int r, bool chk){
    visited[x] = 1;
    if(chk) arr[x] = l++;
    else arr[x] = r--;
    for(auto y: link[x]){
        if(visited[y]) continue;
        if(chk){
            dfs(y, r-sz[y]+1, r, !chk);
            r -= sz[y];
        }
        else{
            dfs(y, l, l+sz[y]-1, !chk);
            l += sz[y];
        }
    }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    fill(visited, visited+n, 0);
    fill(arr, arr+n, 0);
    fill(sz, sz+n, 0);
    for(int i=0; i<n; i++) link[i].clear();
    for(int i=0; i<n-1; i++) link[u[i]].push_back(v[i]), link[v[i]].push_back(u[i]);

    szd(0);
    dfs(0, 0, n-1, 1);

    return vector<int> (arr, arr+n);
}

int find_next_station(int s, int t, vector<int> c) {
    if(s == 0){ /// 루트
        sort(c.begin(), c.end());
        for(auto x: c){
            if(t <= x) return x;
        }
        exit(1);
    }
	else if(c[0] > s){ /// 작은 정점
        sort(c.begin(), c.end());
        if(t < s) return c.back();
        for(auto x: c){
            if(t <= x) return x;
        }
        exit(1);
	}
	else{ /// 큰 정점
        sort(c.rbegin(), c.rend());
        if(t > s) return c.back();
        for(auto x: c){
            if(t >= x) return x;
        }
        exit(1);
	}
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 996 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 884 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 1080 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1029 ms 864 KB Output is correct
2 Correct 645 ms 864 KB Output is correct
3 Runtime error 2 ms 864 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 1072 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -