Submission #604658

#	Time	Username	Problem	Language	Result	Execution time	Memory
604658		Mher	Stations (IOI20_stations)	C++17	52.32 / 100	937 ms	752 KiB

stations

#include <bits/stdc++.h>
#include "stations.h"
#include <vector>

using namespace std;

int sz;
vector<vector<int>> g;
vector<int> labels;
int cnt = 0;

void dfs(int v, int p)
{
    int tin = cnt++;
    for (int to : g[v])
    {
        if (to == p)
            continue;

        dfs(to, v);
    }
    int tout = cnt;
    labels[v] = tin + 1000 * (tout - tin);
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	labels = vector<int>(n);
	sz = n;
	g = vector<vector<int>>(n);
	cnt = 0;
	for (int i = 0; i < n - 1; i++)
    {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    dfs(0, -1);
    return labels;
}

pair<int, int> calc(int x)
{
    return {x % 1000, x / 1000 + x % 1000};
}

bool check(int a, int b)
{
    pair<int, int> ap = calc(a), bp = calc(b);
    return ap.first <= bp.first && ap.second >= bp.second;
}

int find_next_station(int s, int t, vector<int> c) {
    if (!check(s, t))
    {
        for (int to : c)
        {
            if (check(to, s))
                return to;
        }
    }
    else
    {
        for (int to : c)
        {
            if (check(to, t))
                return to;
        }
    }
}

/*
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:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^

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