oj.uz

Submission #1046719

# Submission time Handle Problem Language Result Execution time Memory
1046719 2024-08-06T20:59:20 Z MarwenElarbi Stations (IOI20_stations) C++17
100 / 100
 539 ms 1796 KB 
#include <bits/stdc++.h>
using namespace std;
#include "stations.h"
#define pb push_back
const int nax=10005;
vector<int> adj[nax];
int tin[nax];
int tout[nax];
vector<int> ans(nax);
int timer=-1;
void compute(int x,int p){
    tin[x]=++timer;
    for(auto u:adj[x]){
        if(u==p) continue;
        compute(u,x);
    }
    tout[x]=timer;
    return;
}
void dfs1(int x,int p,int dep,int cnt){
    if(dep==0){
        ans[x]=tin[x]-cnt;
    }
    for(auto u:adj[x]){
        if(u==p) continue;
        dfs1(u,x,1-dep,cnt+(dep==1));
    }
    return;
}
void dfs2(int x,int p,int dep,int cnt){
    if(dep==1){
        ans[x]=tout[x]-cnt;
    }
    vector<int> cur;
    for(auto u:adj[x]){
        cur.pb(u);
    }
    reverse(cur.begin(),cur.end());
    for(auto u:cur){
        if(u==p) continue;
        dfs2(u,x,1-dep,cnt+(dep==1));
    }
    return;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    ans.resize(n);
    timer=-1;
    for (int i = 0; i < n; ++i)
    {
    	adj[i].clear();
    }
    for (int i = 0; i < n-1; i++) {
        int x=u[i];
        int y=v[i];
        adj[x].pb(y);
        adj[y].pb(x);
    }
    compute(0,-1);
    dfs1(0,-1,0,0);
    dfs2(0,-1,0,0);
    return ans;
}

int find_next_station(int s, int t, std::vector<int> c) {
    sort(c.begin(),c.end());
    int lst;
    if(s>c.back()){
        lst=c.back();
        if(t>s) return c[0];
        for (int i = c.size()-1; i >= 0; --i)
        {
            lst=c[i];
            if(c[i]<=t) break;
        }
    }else{
        lst=c[0];
        if(t<s) return c.back();
        for (int i = 0; i < c.size(); ++i)
        {
            lst=c[i];
            if(c[i]>=t) break;
        }
    }
    return lst;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 1452 KB Output is correct
2 Correct 271 ms 1452 KB Output is correct
3 Correct 500 ms 1196 KB Output is correct
4 Correct 379 ms 1196 KB Output is correct
5 Correct 327 ms 1196 KB Output is correct
6 Correct 233 ms 1452 KB Output is correct
7 Correct 257 ms 1452 KB Output is correct
8 Correct 0 ms 1284 KB Output is correct
9 Correct 2 ms 1284 KB Output is correct
10 Correct 1 ms 1292 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 1196 KB Output is correct
2 Correct 270 ms 1208 KB Output is correct
3 Correct 497 ms 1196 KB Output is correct
4 Correct 360 ms 1196 KB Output is correct
5 Correct 312 ms 1196 KB Output is correct
6 Correct 230 ms 1196 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 1452 KB Output is correct
2 Correct 260 ms 1456 KB Output is correct
3 Correct 470 ms 1196 KB Output is correct
4 Correct 391 ms 1248 KB Output is correct
5 Correct 347 ms 1196 KB Output is correct
6 Correct 260 ms 1452 KB Output is correct
7 Correct 278 ms 1452 KB Output is correct
8 Correct 1 ms 1292 KB Output is correct
9 Correct 1 ms 1276 KB Output is correct
10 Correct 0 ms 1284 KB Output is correct
11 Correct 321 ms 1196 KB Output is correct
12 Correct 239 ms 1556 KB Output is correct
13 Correct 264 ms 1700 KB Output is correct
14 Correct 244 ms 1200 KB Output is correct
15 Correct 26 ms 1284 KB Output is correct
16 Correct 40 ms 1288 KB Output is correct
17 Correct 51 ms 1272 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 1196 KB Output is correct
2 Correct 386 ms 1196 KB Output is correct
3 Correct 348 ms 1196 KB Output is correct
4 Correct 0 ms 1284 KB Output is correct
5 Correct 1 ms 1284 KB Output is correct
6 Correct 0 ms 1284 KB Output is correct
7 Correct 349 ms 1196 KB Output is correct
8 Correct 516 ms 1196 KB Output is correct
9 Correct 365 ms 1196 KB Output is correct
10 Correct 321 ms 1196 KB Output is correct
11 Correct 2 ms 1284 KB Output is correct
12 Correct 2 ms 1292 KB Output is correct
13 Correct 2 ms 1284 KB Output is correct
14 Correct 1 ms 1284 KB Output is correct
15 Correct 0 ms 1280 KB Output is correct
16 Correct 287 ms 1200 KB Output is correct
17 Correct 278 ms 1196 KB Output is correct
18 Correct 271 ms 1196 KB Output is correct
19 Correct 275 ms 1196 KB Output is correct
20 Correct 270 ms 1196 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 1452 KB Output is correct
2 Correct 257 ms 1452 KB Output is correct
3 Correct 505 ms 1196 KB Output is correct
4 Correct 390 ms 1196 KB Output is correct
5 Correct 320 ms 1196 KB Output is correct
6 Correct 269 ms 1452 KB Output is correct
7 Correct 244 ms 1452 KB Output is correct
8 Correct 0 ms 1284 KB Output is correct
9 Correct 2 ms 1284 KB Output is correct
10 Correct 1 ms 1292 KB Output is correct
11 Correct 236 ms 1196 KB Output is correct
12 Correct 290 ms 1196 KB Output is correct
13 Correct 539 ms 1196 KB Output is correct
14 Correct 374 ms 1196 KB Output is correct
15 Correct 337 ms 1196 KB Output is correct
16 Correct 242 ms 1196 KB Output is correct
17 Correct 326 ms 1196 KB Output is correct
18 Correct 228 ms 1700 KB Output is correct
19 Correct 236 ms 1560 KB Output is correct
20 Correct 271 ms 1196 KB Output is correct
21 Correct 22 ms 1284 KB Output is correct
22 Correct 39 ms 1284 KB Output is correct
23 Correct 49 ms 1260 KB Output is correct
24 Correct 3 ms 1292 KB Output is correct
25 Correct 3 ms 1292 KB Output is correct
26 Correct 2 ms 1280 KB Output is correct
27 Correct 1 ms 1284 KB Output is correct
28 Correct 0 ms 1284 KB Output is correct
29 Correct 308 ms 1320 KB Output is correct
30 Correct 298 ms 1196 KB Output is correct
31 Correct 284 ms 1196 KB Output is correct
32 Correct 281 ms 1196 KB Output is correct
33 Correct 293 ms 1196 KB Output is correct
34 Correct 172 ms 1568 KB Output is correct
35 Correct 223 ms 1452 KB Output is correct
36 Correct 234 ms 1608 KB Output is correct
37 Correct 247 ms 1300 KB Output is correct
38 Correct 251 ms 1304 KB Output is correct
39 Correct 275 ms 1304 KB Output is correct
40 Correct 256 ms 1308 KB Output is correct
41 Correct 266 ms 1560 KB Output is correct
42 Correct 28 ms 1280 KB Output is correct
43 Correct 60 ms 1276 KB Output is correct
44 Correct 66 ms 1196 KB Output is correct
45 Correct 85 ms 1232 KB Output is correct
46 Correct 159 ms 1196 KB Output is correct
47 Correct 185 ms 1196 KB Output is correct
48 Correct 26 ms 1796 KB Output is correct
49 Correct 24 ms 1400 KB Output is correct