Submission #683739

#	Time	Username	Problem	Language	Result	Execution time	Memory
683739		sharaelong	Stations (IOI20_stations)	C++17	100 / 100	912 ms	768 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int MAX_N = 1000;
vector<int> adj[MAX_N];
int depth[MAX_N];
int tour[MAX_N];
int tour_cnt = 0;

void dfs(int here, int parent = -1) {
    if (~depth[here] & 1) tour[here] = tour_cnt;
    for (int there: adj[here]) {
        if (there != parent) {
            depth[there] = depth[here] + 1;
            if (~depth[here] & 1) tour_cnt++;
            dfs(there, here);
        }
    }
    if (depth[here] & 1) {
        tour[here] = tour_cnt;
    } else {
        tour_cnt++;
    }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for (int i=0; i<n; ++i) adj[i].clear();
    tour_cnt = 0;
    memset(depth, 0, sizeof depth);
    
    for (int i=0; i<n-1; ++i) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    dfs(0);
    assert(tour_cnt == n);

	vector<int> labels(n);
	for (int i=0; i<n; i++) labels[i] = tour[i];
    // cout << endl;
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    if (c.size() == 1) return c[0];
    // s is start
    if (s < c[0]) {
        if (s < t && t <= c[c.size()-2]) {
            for (int i=0; i+1<c.size(); ++i) {
                if (t <= c[i]) return c[i];
            }
        } else {
            return c.back();
        }
    } else {
        if (s > t && t >= c[1]) {
            for (int i=1; i+1<c.size(); ++i) {
                if (c[i] <= t && t < c[i+1]) return c[i];
            }
            return c.back();
        } else {
            return c[0];
        }
    }
    assert(false);
}

Compilation message (stderr)

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

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