Submission #306899

#TimeUsernameProblemLanguageResultExecution timeMemory
306899giorgikobStations (IOI20_stations)C++14
Compilation error
0 ms0 KiB
//#include "stations.h" #include <cstdio> #include <cassert> #include <map> #include <vector> #include <algorithm> #include<bits/stdc++.h> #define ll long long #define ff first #define ss second #define pb push_back using namespace std; static int max_label = 0; static int r, n, k, q; static std::vector<int> u, v, labels, answers; static std::map<int, int> reverse_labels; static std::vector<std::vector<int>> adjlist; static int s, t, w; static std::vector<int> c; const int N = 1e3+5; vector<int>gr[N]; int cnt = 0; int fix[N]; //int c = 0; void dfs(int x, vector<int>&v){ fix[x] = 1; v[x] = cnt; cnt++; for(auto to : gr[x]){ if(fix[to]) continue; dfs(to,v); } } std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) { std::vector<int> labels(n,0); for(int i = 0; i < u.size(); i++){ int x = u[i]; int y = v[i]; gr[x].pb(y); gr[y].pb(x); } cnt = 0; for(int i = 0; i < n; i++){ if(gr[i].size() == 1){ dfs(i,labels); break; } } for(int i = 0; i < n; i++){ for(int j = i+1; j < n; j ++){ assert(labels[i] != labels[j]); } } //for(auto x : labels) cout << x <<" "; cout << endl; //if(labels[0] == 0) dfs(0,labels); for(int i = 0; i < n; i++) gr[i].clear(); return labels; } int find_next_station(int s, int t, std::vector<int> c) { if(c.size() == 1) return c[0]; if(s > t) return c[0]; return c[1]; } int main() { assert(scanf("%d", &r) == 1); for (int tc = 0; tc < r; tc++) { assert(scanf("%d%d", &n, &k) == 2); u.resize(n - 1); v.resize(n - 1); adjlist.clear(); adjlist.resize(n); for (int i = 0; i < n - 1; i++) { assert(scanf("%d%d", &u[i], &v[i]) == 2); adjlist[u[i]].push_back(v[i]); adjlist[v[i]].push_back(u[i]); } labels = label(n, k, u, v); if ((int)labels.size() != n) { printf("Number of labels not equal to %d\n", n); exit(0); } reverse_labels.clear(); for (int i = 0; i < n; i++) { if (labels[i] < 0 || labels[i] > k) { printf("Label not in range 0 to %d\n", k); exit(0); } if (reverse_labels.find(labels[i]) != reverse_labels.end()) { printf("Labels not unique\n"); exit(0); } reverse_labels[labels[i]] = i; if (labels[i] > max_label) { max_label = labels[i]; } } assert(scanf("%d", &q) == 1); for (int i = 0; i < q; i++) { assert(scanf("%d%d%d", &s, &t, &w) == 3); c.clear(); for (int v : adjlist[s]) { c.push_back(labels[v]); } std::sort(c.begin(), c.end()); int answer = find_next_station(labels[s], labels[t], c); if (!std::binary_search(c.begin(), c.end(), answer)) { printf("Label %d returned by find_next_station not found in c\n", answer); exit(0); } answers.push_back(reverse_labels[answer]); } } printf("%d\n", max_label); for (int index : answers) { printf("%d\n", index); } exit(0); }

Compilation message (stderr)

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~
/tmp/ccKRJoY1.o: In function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccDFr43X.o:stations.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status