Submission #615915

#	Time	Username	Problem	Language	Result	Execution time	Memory
615915		eNGy	기지국 (IOI20_stations)	C++17	100 / 100	986 ms	740 KiB

stations

#include <bits/stdc++.h>
#define con(x) (cerr << __LINE__ << ": " << #x << ' ' << (x) << endl, (x))
#define vis() (cerr << __LINE__ << endl)
#define ll long long
#define f first
#define s second
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;

void dfs(int n, int p, int d, int &e, vector<int> &L, vector<vector<int>> &G){
    if(d%2 == 0) L[n] = e++;
    for(int v: G[n]){
        if(v != p){
            dfs(v, n, d+1, e, L, G);
        }
    }
    if(d%2 != 0) L[n] = e++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){
    vector<vector<int>> G(n);
    for(int i=0; i<n-1; i++){
		G[u[i]].pb(v[i]);
		G[v[i]].pb(u[i]);
	}

    vector<int> L(n);
    int e = 0;

    dfs(0, -1, 0, e, L, G);

    //for(int l: L) cout << l << ' '; cout << endl;

    return L;
}

int find_next_station(int s, int t, std::vector<int> c){
    int N = c.size();
    if(N == 1) return c[0];

    pair<int, int> S;
    vector<pair<int, int>> C(N);

    if(c[0] > s){
        // s open

        C[N-1] = {-1, -1};

        S.s = c[N-2];
        S.f = s;

        if(t < S.f || t > S.s)
            return c[N-1];

        for(int i=N-2; i>0; i--){
            C[i].s = c[i];
            C[i].f = c[i-1] + 1;
        }

        C[0].f = s + 1;
        C[0].s = c[0];

    }else{
        // s close
        C[0] = {-1, -1};

        S.f = c[1];
        S.s = s;

        if(t < S.f || t > S.s)
            return c[0];

        for(int i=1; i<N-1; i++){
            C[i].f = c[i];
            C[i].s = c[i+1] - 1;
        }

        C[N-1].f = c[N-1];
        C[N-1].s = s - 1;

    }

    //cout << S.f << ' ' << S.s << endl;
    for(int i=0; i<N; i++){
        //cout << C[i].f << ' ' << C[i].s << endl;
        if(C[i].f <= t && t <= C[i].s)
            return c[i];
    }
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:47:31: warning: control reaches end of non-void function [-Wreturn-type]
   47 |     vector<pair<int, int>> C(N);
      |                               ^

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