Submission #620051

#	Time	Username	Problem	Language	Result	Execution time	Memory
620051		sokratisi	Stations (IOI20_stations)	C++17	0 / 100	851 ms	420 KiB

stations

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

using namespace std;

int cur = 1;

void dfs(const vector<vector<int>>& adj, vector<bool>& vis, vector<int>& labels, int s, const int& m, int o) {
    if (s == o) labels[s] = 0;
    vis[s] = true;
    if (adj[s].size() == 1) {
        if(adj[s][0] != o) labels[s] = labels[adj[s][0]] + m;
        else labels[s] = cur++;
    }
    else {
        if(vis[adj[s][0]]) {
            if(adj[s][0] != o) labels[s] = labels[adj[s][0]] + m;
            else labels[s] = cur++;
        }
        else {
            if(adj[s][1] != o) labels[s] = labels[adj[s][1]] + m;
            else labels[s] = cur++;
        }
    }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    cur = 1;
	vector<vector<int>> adj(n);
    for (int i = 0; i < u.size(); i++) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    int s = 0;
    for (int i = 0; i < n; i++) if(adj[i].size() > 2) s = i;
    vector<int> labels(n);
    vector<bool> vis(n, false);
    int m = adj[s].size();
    dfs(adj, vis, labels, s, m, s);
    
    return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    if (!s) {
        int m = c.size();
        int mod = t % m;
        for (auto u: c) {
            if ((u % m) == mod) return u;
        }
    }
    if (c.size() == 1) return c[0];
    if (!c[0]) {
        if (!t) return c[0];
        else return c[1];
    }
    if (!c[1]) {
        if (!t) return c[1];
        else return c[0];
    }
    int m;
    if (c[0] < s) {
        m = s - c[0];
        if ((s % m) == (t % m)) {
            if (t < s) return c[0];
            return c[1];
        }
        return c[0];
    }
    m = s - c[1];
    if ((s % m) == (t % m)) {
        if (t < s) return c[1];
        return c[0];
    }
    return c[1];
}

// int main() {
//     int n, k;
//     scanf("%d%d", &n, &k);

//     vector<int> u(n-1);
//     vector<int> v(n-1);
//     for (int i = 0; i < n - 1; i++) {
//         scanf("%d%d", &u[i], &v[i]);
//     }

//     label(n, k, u, v);

//     return 0;
// }

Compilation message (stderr)

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < u.size(); i++) {
      |                     ~~^~~~~~~~~~

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