| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 405734 |
2021-05-16T20:57:03 Z |
ly20 |
Stations (IOI20_stations) |
C++17 |
|
0 ms |
0 KB |
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1123;
int t, ent[MAXN], sd[MAXN], prof[MAXN];
vector <int> grafo[MAXN];
void dfs(int v, int p) {
ent[v] = t;
t++;
for(int i = 0; i < grafo[v].size(); i++) {
int viz = grafo[v][i];
if(viz == p) continue;
prof[viz] = prof[v] + 1;
dfs(viz, v);
}
sd[v] = t;
t++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels;
for(int i = 0; i < n; i++) {
grafo[u[i]].push_back(v[i]);
grafo[v[i]].push_back(u[i]);
}
dfs(0, 0);
set <pair <int, int> > s;
map <pair <int, int>, int> mp;
for (int i = 0; i < n; i++) {
if(prof[i] % 2 == 0) s.insert(make_pair(ent[i], 0));
else s.insert(make_pair(sd[i], 1));
}
int at = 0;
set <pair <int, int> > :: iterator it;
for(it = s.begin(); it != s.end(); it++) {
mp[*it] = at++;
}
for(int i = 0; i < n; i++) {
pair <int, int> a;
if(prof[i] % 2 == 0) a = make_pair(ent[i], 0);
else a = make_pair(sd[i], 1);
labels.push_back(mp[a]);
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int tp, rs, mn = 1123, mx = 0;
if(c.size() == 1) return c[0];
for(int i = 0; i < c.size(); i++) {
int viz = c[i];
mn = min(viz, mn);
mx = max(viz, mx);
if(viz < s) tp = 1;
if(viz > s) tp = 0;
}
vector <int> temp;
if(tp == 0) {
rs = mx;
temp.push_back(s);
for(int i = 0; i < c[i].size(); i++) {
if(c[i] == mx) {
mx = -mx;
continue;
}
temp.push_back(c[i]);
}
sort(temp.begin(), temp.end());
for(int i = 1; i < temp.size(); i++) {
if(t >= temp[i - 1] + 1 && t <= temp[i]) {
rs = temp[i];
}
}
}
else {
rs = mn;
temp.push_back(s);
for(int i = 0; i < c[i].size(); i++) {
if(c[i] == mn) {
mn = -mn;
continue;
}
temp.push_back(c[i]);
}
sort(temp.begin(), temp.end());
for(int i = 0; i < temp.size() - 1; i++) {
if(t >= temp[i] && t <= temp[i + 1] + 1) {
rs = temp[i];
}
}
}
return rs;
}
Compilation message
stations.cpp: In function 'void dfs(int, int)':
stations.cpp:10:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for(int i = 0; i < grafo[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:60:33: error: request for member 'size' in 'c.std::vector<int>::operator[](((std::vector<int>::size_type)i))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
60 | for(int i = 0; i < c[i].size(); i++) {
| ^~~~
stations.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 1; i < temp.size(); i++) {
| ~~^~~~~~~~~~~~~
stations.cpp:77:33: error: request for member 'size' in 'c.std::vector<int>::operator[](((std::vector<int>::size_type)i))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
77 | for(int i = 0; i < c[i].size(); i++) {
| ^~~~
stations.cpp:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i = 0; i < temp.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~~
