Submission #777025

#	Time	Username	Problem	Language	Result	Execution time	Memory
777025		_martynas	Stations (IOI20_stations)	C++14	0 / 100	620 ms	676 KiB

stations

#include "stations.h"
#include <vector>
#include <iostream>

using namespace std;

void traverse(int u, int p, vector<int> &sz, vector<vector<int>> &adj) {
    sz[u] = 1;
    for(int v : adj[u]) if(v != p) {
        traverse(v, u, sz, adj);
        sz[u] += sz[v];
    }
}

/*
increment timer when going down if par == 0
increment timer when going up if par == 1
*/
void bipartite_labeling(int u, int p, int par, int &timer, vector<int> &sz,
                        vector<int> &labels, vector<vector<int>> &adj) {
    labels[u] = par ? timer+sz[u]-1 : timer;
    if(par == 0) timer++;
    for(int v : adj[u]) if(v != p) {
        bipartite_labeling(v, u, 1-par, timer, sz, labels, adj);
    }
    if(par == 1) timer++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n), sz(n);
	vector<vector<int>> adj(n);
    for(int i = 0; i < (int)u.size(); i++) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    traverse(0, -1, sz, adj);
    bipartite_labeling(0, -1, 0, *new int{0}, sz, labels, adj);
	return labels;
}

// c is sorted in ascending order
int find_next_station(int s, int t, vector<int> c) {
    if(s == 0) {
        // at root
        for(int x : c) if(x >= t) return x;
    }
    else {
        // 1 neighbor goes towards root, some down the tree
        if(c.size() == 1) return c[0];
        // I. determine which type of vertex is s
        if(c.back() < s) {
            // par = 1
            // minimum label is toward the root
            int up = c[0];
            c.erase(c.begin());
            if(t >= s) return up;
            int where = up;
            for(int x : c) if(x <= t) where = x;
            return where;
        }
        else {
            // par = 0
            // maximum label is toward the root
            int up = c.back();
            c.pop_back();
            if(t < s) return up;
            for(int x : c) if(x > t) return x;
            return up;
        }
    }
	return -1;
}

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