Submission #682021

#TimeUsernameProblemLanguageResultExecution timeMemory
682021junkbotStations (IOI20_stations)C++14
100 / 100
884 ms1356 KiB
#include "stations.h" #include <bits/stdc++.h> using namespace std; #define D(x...) fprintf(stderr, x) #define D(x...) const int MAX_N = 1005; const int UNLABELLED = -1; const int PENDING = -2; struct Solve { int upto; vector<vector<int>> adjlist; vector<int> labels; Solve(int n, vector<int> u, vector<int> v) : upto(0), adjlist(n), labels(n) { for (auto i=0;i<u.size();i++) { adjlist[u[i]].push_back(v[i]); adjlist[v[i]].push_back(u[i]); } fill(labels.begin(), labels.end(), UNLABELLED); } // label everything in u's subtree. void go(int u, bool isPre) { if (labels[u] != UNLABELLED) return; labels[u] = PENDING; if (isPre) labels[u] = getNext(); for (auto v: adjlist[u]) go(v, !isPre); if (!isPre) labels[u] = getNext(); } int getNext() { int ret = upto; upto++; return ret; } }; std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) { auto solver = new Solve(n, u, v); solver->go(0, true); vector<int> ret; for (auto l: solver->labels) { ret.push_back(l); } D("labels:"); for (auto l: solver->labels) { D(" %d", l); } D("\n"); return ret; } int find_next_station(int s, int t, std::vector<int> c) { if (s < c.front()) { // preorder int left_exclusive = s; for (auto i=0;i<c.size()-1;i++) { auto l = c[i]; if (left_exclusive < t && t <= l) return l; left_exclusive = l; } return c.back(); } else { // postorder int right_exclusive = s; for (auto i=c.size()-1;i>0;i--) { auto l = c[i]; if (l <= t && t < right_exclusive) return l; right_exclusive = l; } return c.front(); } }

Compilation message (stderr)

stations.cpp:7: warning: "D" redefined
    7 | #define D(x...)
      | 
stations.cpp:6: note: this is the location of the previous definition
    6 | #define D(x...) fprintf(stderr, x)
      | 
stations.cpp: In constructor 'Solve::Solve(int, std::vector<int>, std::vector<int>)':
stations.cpp:19:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for (auto i=0;i<u.size();i++) {
      |                       ~^~~~~~~~~
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:52:15: warning: unused variable 'l' [-Wunused-variable]
   52 |     for (auto l: solver->labels) {
      |               ^
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (auto i=0;i<c.size()-1;i++) {
      |                       ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...