제출 #1166433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166433		TsotneSV	기지국 (IOI20_stations)	C++17	100 / 100	308 ms	628 KiB

stations

#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋       
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=2e5+5; 
const ll inf=1e9,INF=1e18; 

void dfs(int v,int p,int d,int &timer,vector<vi> &g,vi &in,vi &out,vi &val) {

    in[v] = timer++;

    for(int i : g[v]) {
        if(i == p) continue;
        dfs(i,v,d+1,timer,g,in,out,val);
    } out[v] = timer++;

    if(d % 2) val[v] = in[v];
    else val[v] = out[v]; 

}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	
    vector<vi> g(n); vi in(n),out(n),val(n),cmp(2*n+1);

    for(int i=0;i<n-1;i++) g[u[i]].pb(v[i]),g[v[i]].pb(u[i]);

    int timer = 0; 
    
    dfs(0,-1,0,timer,g,in,out,val);

    vi tmp = val; sort(all(tmp));

    for(int i=0;i<n;i++) cmp[tmp[i]] = i;
    for(int i=0;i<n;i++) val[i] = cmp[val[i]];

    return val;
}

int find_next_station(int s, int t, vector<int> c) {
    
    bool odd = 1; sort(all(c));

    for(int i : c) {
        odd &= (i > s);
    }

    if(odd) {

        for(int i : c) {
            if(t >= s and t <= i) return i;
        } return c.back();

    } else {

        if(t > s) return c.front();

        for(int i=1;i<c.size()-1;i++) {
            if(c[i] <= t and t < c[i+1]) return c[i];
        } 
        
        if(c.back() <= t and t < s) return c.back();
        return c.front();

    }

}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 61 / 61