제출 #604685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604685		rrrr10000	기지국 (IOI20_stations)	C++14	100 / 100	1095 ms	800 KiB

stations

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}

vector<int> label(int n,int k,vector<int> a,vector<int> b){
    vvi g(n);
    rep(i,n-1){
        g[a[i]].pb(b[i]);g[b[i]].pb(a[i]);
    }
    vp dp(n);
    dp[0]=P(0,n-1);
    vector<int> res(n);
    vi sub(n,1);
    function<ll(ll,ll)> dfs0=[&](ll i,ll p){
        for(ll x:g[i])if(x!=p)sub[i]+=dfs0(x,i);
        return sub[i];
    };dfs0(0,-1);
    function<void(ll,ll,ll)> dfs1=[&](ll i,ll p,ll d){
        if(d%2)res[i]=dp[i].fi++;
        else res[i]=dp[i].se--;
        for(ll x:g[i])if(x!=p){
            dp[x]=P(dp[i].fi,dp[i].fi+sub[x]-1);
            dp[i].fi+=sub[x];
            dfs1(x,i,d+1);
        }
    };dfs1(0,-1,0);
    return res;
}
int find_next_station(int s,int t,vector<int> c){
    for(int x:c)if(x==t)return t;
    if(c.size()==1)return c[0];
    if(s<c[0]){
        if(t<s||t>c.back())return c.back();
        rep(i,c.size())if(c[i]>t)return c[i];
    }
    if(t>s||t<c[0])return c[0];
    for(int i=c.size()-1;i>=0;i--)if(c[i]<t)return c[i];
}

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

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
   52 | }
      | ^

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