| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 405738 |
2021-05-16T21:01:50 Z |
ly20 |
Stations (IOI20_stations) |
C++17 |
|
1297 ms |
804 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[i].clear();
for(int i = 0; i < u.size(); i++) {
grafo[u[i]].push_back(v[i]);
grafo[v[i]].push_back(u[i]);
}
prof[0] = 0;
t = 0;
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.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]) {
return temp[i];
}
}
}
else {
rs = mn;
temp.push_back(s);
for(int i = 0; i < c.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) {
return 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 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i = 0; i < u.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 1; i < temp.size(); i++) {
| ~~^~~~~~~~~~~~~
stations.cpp:80:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 0; i < temp.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~~
stations.cpp:60:2: warning: 'tp' may be used uninitialized in this function [-Wmaybe-uninitialized]
60 | if(tp == 0) {
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
507 ms |
804 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
552 ms |
660 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
800 ms |
656 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1297 ms |
400 KB |
Output is correct |
| 2 |
Correct |
791 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
817 ms |
492 KB |
Wrong query response. |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
478 ms |
640 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
