Submission #804962

#	Time	Username	Problem	Language	Result	Execution time	Memory
804962		PixelCat	Stations (IOI20_stations)	C++14	100 / 100	802 ms	804 KiB

stations

#include "stations.h"

#ifdef NYAOWO
#include "stub.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1000;

vector<int> adj[MAXN + 10];
int ids[MAXN + 10];
int siz[MAXN + 10];
int cur_id;

void dfs1(int n, int p, int d) {
    if(d) {
        ids[n] = cur_id;
        cur_id++;
    }
    siz[n] = 0;
    for(auto &i:adj[n]) if(i != p) {
        dfs1(i, n, 1 - d);
        siz[n] += siz[i] + 1;
    }
    if(!d) {
        ids[n] = cur_id;
        cur_id++;
    }
}

int encode(int id, int sz) {
    return id * MAXN + sz;
}
int encode(pii p) {
    return encode(p.F, p.S);
}
pii decode(int x) {
    return pii(x / MAXN, x % MAXN);
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    For(i, 0, n - 1) {
        adj[i].clear();
    }
    int m = sz(u);
    For(i, 0, m - 1) {
        adj[u[i]].eb(v[i]);
        adj[v[i]].eb(u[i]);
    }
    cur_id = 0;
    dfs1(0, 0, 0);
    vector<int> labels(n);
    For(i, 0, n - 1) labels[i] = ids[i];
    return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    if(sz(c) == 1) return c[0];
    int n = sz(c);
    if(s < c[0]) {
        int p = c.back();
        if(t <= s || t >= p) return p;
        for(auto &i:c) if(t <= i) return i;
    } else {
        reverse(all(c));
        int p = c.back();
        if(t <= p || t >= s) return p;
        for(auto &i:c) if(t >= i) return i;
    }
    return -1;
}

/*

1
5 10
0 1
1 2
1 3
2 4
2
2 0 1
1 3 3

*/

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:72:9: warning: unused variable 'n' [-Wunused-variable]
   72 |     int n = sz(c);
      |         ^

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