제출 #927179

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

stations

#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
#define ms(a) memset(a,0,sizeof (a))
namespace {
    vector <ll> g[200100];
    ll sus[200100];
    ll depth[200100];
    ll timeDFS;
    void dfs(ll u,ll p){
        depth[u] = depth[p]+1;
        if (depth[u]&1)sus[u]=timeDFS++;
        for (auto v:g[u]){
            if (v!=p)dfs(v,u);
        }
        if ((depth[u]&1)==0)sus[u]=timeDFS++;
    }
}
std::vector<ll> label(ll n, ll k, std::vector<ll> u, std::vector<ll> v) {
	std::vector<ll> labels(n);
	for (ll i = 0;i < n;i ++)g[i].clear();
	timeDFS = 0;
	for (ll i = 0;i <= n - 2;i ++){
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
	}
	dfs(0,0);
	for (ll i = 0;i < n;i ++){
        labels[i] = sus[i];
	}
	return labels;
}

ll find_next_station(ll s, ll t, std::vector<ll> c) {
    if (s>c[0]){
        ll p = *c.begin();
        c.erase(c.begin());
        c.push_back(s+1);
        for (ll i = 0;i + 1 < sz(c);i ++){
            ll l=c[i],r=c[i+1]-1;
            if (l <= t && t <= r){
                return l;
            }
        }
        return p;
    }
    else{
        ll p = c.back();
        if (s>0)c.pop_back();
        c.insert(c.begin(),s-1);
        for (ll i = 0;i + 1 < sz(c);i ++){
            ll l=c[i]+1,r=c[i+1];
            if (l <= t && t <= r){
                return c[i+1];
            }
        }
        return p;
    }
}

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