Submission #405255

#	Time	Username	Problem	Language	Result	Execution time	Memory
405255		balbit	기지국 (IOI20_stations)	C++14	0 / 100	1018 ms	956 KiB

stations

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

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){ cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){ cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT


const int maxn = 1e3+5;

vector<int> g[maxn];
std::vector<int> re;
set<int> here[maxn];
int sz[maxn];
void szdfs(int v, int p) {
    sz[v] =1;
    for (int u : g[v]) {
        if (u == p) continue;
        szdfs(u,v);
        sz[v] += sz[u];
    }
}

void dfs(int v, int p, bool big) {
    sort(ALL(g[v]), [&](int a, int b){return sz[a] < sz[b];});
    if (g[v].back() == p) g[v].pop_back();
    if( big) {
        re[v] = *(here[v].rbegin());
    }else{
        re[v] = *(here[v].begin());
    }
    here[v].erase(re[v]);
    for (int u : g[v]) {
        assert(u != p);
        if (u == g[v].back()) here[u].swap(here[v]);
        else{
            REP(j, sz[u]) {
                here[u].insert(*here[v].begin());
                here[v].erase(here[v].begin());
            }
        }
        dfs(u,v,big^1);
    }
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
//    cout<<"HIHOEIHFOI"<<endl;
	re.resize(n);
//	return re;
    REP(i,n) g[i].clear();
    REP(i,n) here[i].clear();

    REP(i,n-1) {
        g[u[i]].pb(v[i]);
        g[v[i]].pb(u[i]);
    }
    szdfs(0,-1);
    REP(i,n) here[0].insert(i);
    dfs(0,-1,0);
//    for (int i = 0; i<n; ++i) {
//        cout<<i<<": "<<re[i]<<endl;
//    }
    return re;
}

int find_next_station(int s, int t, std::vector<int> c) {
//    return c[0];
	if (SZ(c) == 1) {
        return c[0];
	}
	sort(ALL(c));
	if (s == 0) {
        for (int b : c) {
            if (b >= t) return b;
        }
        assert(0);
	}
	if (SZ(c) == 2) {
        if (c[0] > s && c[1] > s) {
            return min(c[0], c[1]);
        }else{
            assert(c[0] < s && c[1] < s);
            return max(c[0], c[1]);
        }
	}
    int numbig = 0;
    for (int b : c) {
        if (b > s) numbig++;
    }
//    cout<<"Hey"<<numbig<<endl;
    if (numbig > 0) {
        // bigs are the upper bound
        int prv = s;
        for (int b : c) {
            if (t<=b && t> prv) {
                return b;
            }
            prv = b;
        }
        return c.back();
        // return the last one
    }else{
        // smalls are the lower bound
//        cout<<"smol!"<<endl;
        reverse(ALL(c));
        int prv = s;
        for (int b : c) {
            if (t>=b && t< prv) {
                return b;
            }
            prv = b;
        }
        return c.back();
    }
}






/*
1
6 1000
0 1
1 2
2 3
3 4
1 5
4
3 5 -1
0 4 -1
1 4 -1
2 0 -1
*/

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