제출 #1367957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1367957		asli_bg	기지국 (IOI20_stations)	C++20	100 / 100	291 ms	632 KiB

stations

#include <bits/stdc++.h>
using namespace std;

//#define int long long

#include "stations.h"

#define fi first
#define se second

#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define sp <<' '<<

#define mid (l+r)/2

#define all(x) x.begin(),x.end()
#define carp(a,b) ((a%MOD)*(b%MOD))%MOD
#define topla(a,b) ((a%MOD)+(b%MOD))%MOD

#define pb push_back

#define DEBUG(x) cout<<#x sp x<<endl;
#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;

const int MAXN=1e3+6;
const int INF=1e9+7;

int timer;
int tin[MAXN], tout[MAXN];
vll adj[MAXN];
vi ans;

void dfs(int nd,int ata,bool f){
    if(f){
        tin[nd]=timer++;
        ans[nd]=tin[nd];
    }
    for(auto kom:adj[nd]){
        if(kom==ata) continue;
        dfs(kom,nd,!f);
    }
    if(!f){
        tout[nd]=timer++;
        ans[nd]=tout[nd];
    }
}

vi label(int n, int k, vi u, vi v){
    ans.resize(n,0);

    FOR(i,n) adj[i].clear();

    FOR(i,n-1){
        adj[u[i]].pb(v[i]);
        adj[v[i]].pb(u[i]);
    }

    timer=1;
    dfs(0,-1,true);

    return ans;
}

int find_next_station(int s, int t, vi c){
    //c sortedmış
    bool in=true;
    for(auto el:c){
        if(s>el){
            in=false;
            break;
        }
    }

    if(in){
        //tin i kayıtlı nodesa
        int deg=c.back();
        c.pop_back();

        int once=s;
        int cur;
        for(auto el:c){
            cur=el;
            if(once<t and t<=cur){
                return el;
            }
        }

        return deg;
    }   
    else{
        //tout ı kayıtlı nodesa
        int once=s;
        int cur;
        reverse(all(c));

        int deg=c.back();
        c.pop_back();

        for(auto el:c){
            cur=el;
            if(cur<=t and t<once){
                return el;
            }
        }

        return deg;
    }
}

• 서브태스크 1: 5 / 5
• 서브태스크 2: 8 / 8
• 서브태스크 3: 16 / 16
• 서브태스크 4: 10 / 10
• 서브태스크 5: 61 / 61