제출 #1367822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1367822		asli_bg	기지국 (IOI20_stations)	C++20	10 / 100	300 ms	556 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];
void dfs(int nd,int ata){
    tin[nd]=timer++;
    for(auto kom:adj[nd]){
        if(kom==ata) continue;
        dfs(kom,nd);
    }
    tout[nd]=timer++;
}

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

    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);

    FOR(i,n){
        ans[i]=tin[i];
        ans[i]*=100;
        ans[i]+=tout[i];

    }

    return ans;
}

pii solve(int& x){
    return {x/100,x%100};
}

bool isata(pii a,pii b){
    return (a.fi<=b.fi and a.se>=b.se); 
}

int find_next_station(int s, int t, vi c) {
    pii bir=solve(s);
    pii iki=solve(t);

    //cout<<bir.fi sp bir.se<<endl;
    //cout<<iki.fi sp iki.se<<endl;

    for(auto el:c) if(el==t) return el;

    if(isata(bir,iki)){
        //aşağı in
        for(auto el:c){
            if(!isata(solve(el),bir) and isata(solve(el),iki)){
                return el;
            }
        }
    }
    else{
        //atama çık
        for(auto el:c){
            if(isata(solve(el),bir)){
                return el;
            }
        }
    }

    return 0;
}

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