Submission #1186312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186312		Swan	Stations (IOI20_stations)	C++20	100 / 100	304 ms	616 KiB

stations

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <optional>
//#define int long long
#define INP freopen("subrev.in","r",stdin)
#define OUTP freopen("subrev.out","w",stdout)
using ld = long double;
using LD = ld;
 
using namespace std;

const int maxn = 1200;

vector<vector<int> > v;
int lab[maxn];
int sz[maxn];

void dfs1(int u, int p = -1) {
    sz[u] = 1;

    for (auto a : v[u]) {
        if (a == p) continue;
        dfs1(a, u);
        sz[u] += sz[a];
    }
}

int cur = 0;

void dfs2(int u, bool isMin = true, int p = -1) {


    if (isMin || (p != -1 && v[u].size() == 1)) {
        lab[u] = cur++;
    } else {
        lab[u] = cur + sz[u] - 1;
    }

    if ((p != -1 && v[u].size() == 1)) return;

    for (auto a : v[u]) {
        if (a == p) continue;
        dfs2(a, !isMin, u);
    }

    if (!isMin) {
        cur++;
    }
}

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

    if (s < c[0]) {
        int last = s + 1;
        for (int i = 0; i < c.size() - 1; i++) {
            if (c[i] == last ){
                if (c[i] == t) return c[i];
                else {
                    last++;
                    continue;
                }
            }

            int r = c[i];

            if (t >= last && t <= r) return c[i];

            last = c[i] + 1;
        }

        return c.back();
    } else {
        int r = s - 1;
        for (int i = c.size() - 1; i > 0; i--) {
            if (c[i] == r) {
                if (c[i] == t) return c[i];
                else {
                    r--;
                    continue;
                }
            }

            int l = c[i];

            if (t >= l && t <= r) return c[i];
            r = c[i] - 1;
        }

        return c[0];
    }
}

vector<int> label(int n, int k, vector<int> a, vector<int> b) {
    v.clear();
    v.resize(a.size() + 10);
    cur = 0;

    for (int i = 0; i < a.size() + 10; i++) {
        sz[i] = 0;
        lab[i] = 0;
    }

    for (int i = 0; i < a.size(); i++) {
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }

    dfs1(0);

    dfs2(0);

    vector<int> res;

    for (int i = 0; i < a.size() + 1; i++) res.push_back(lab[i]);

    return res;
}

/*

void solve() {
    vector<int> res = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});

    for (int i = 0; i < res.size(); i++) cout << i << ' ' << res[i] << endl;

    cout << find_next_station(4, 2, {0, 1, 3});
}


int main() {
    ios_base::sync_with_stdio(0);
    solve();
}
    
*/

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