oj.uz

Submission #927179

# Submission time Handle Problem Language Result Execution time Memory
927179 2024-02-14T11:02:59 Z vjudge1 Stations (IOI20_stations) C++17
100 / 100
 574 ms 13964 KB 
#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
#define ms(a) memset(a,0,sizeof (a))
namespace {
    vector <ll> g[200100];
    ll sus[200100];
    ll depth[200100];
    ll timeDFS;
    void dfs(ll u,ll p){
        depth[u] = depth[p]+1;
        if (depth[u]&1)sus[u]=timeDFS++;
        for (auto v:g[u]){
            if (v!=p)dfs(v,u);
        }
        if ((depth[u]&1)==0)sus[u]=timeDFS++;
    }
}
std::vector<ll> label(ll n, ll k, std::vector<ll> u, std::vector<ll> v) {
	std::vector<ll> labels(n);
	for (ll i = 0;i < n;i ++)g[i].clear();
	timeDFS = 0;
	for (ll i = 0;i <= n - 2;i ++){
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
	}
	dfs(0,0);
	for (ll i = 0;i < n;i ++){
        labels[i] = sus[i];
	}
	return labels;
}

ll find_next_station(ll s, ll t, std::vector<ll> c) {
    if (s>c[0]){
        ll p = *c.begin();
        c.erase(c.begin());
        c.push_back(s+1);
        for (ll i = 0;i + 1 < sz(c);i ++){
            ll l=c[i],r=c[i+1]-1;
            if (l <= t && t <= r){
                return l;
            }
        }
        return p;
    }
    else{
        ll p = c.back();
        if (s>0)c.pop_back();
        c.insert(c.begin(),s-1);
        for (ll i = 0;i + 1 < sz(c);i ++){
            ll l=c[i]+1,r=c[i+1];
            if (l <= t && t <= r){
                return c[i+1];
            }
        }
        return p;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 13128 KB Output is correct
2 Correct 275 ms 13128 KB Output is correct
3 Correct 545 ms 12972 KB Output is correct
4 Correct 404 ms 12972 KB Output is correct
5 Correct 371 ms 13404 KB Output is correct
6 Correct 283 ms 13124 KB Output is correct
7 Correct 252 ms 12968 KB Output is correct
8 Correct 5 ms 13060 KB Output is correct
9 Correct 6 ms 13060 KB Output is correct
10 Correct 3 ms 13060 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 13076 KB Output is correct
2 Correct 330 ms 13028 KB Output is correct
3 Correct 556 ms 12972 KB Output is correct
4 Correct 391 ms 12972 KB Output is correct
5 Correct 397 ms 12972 KB Output is correct
6 Correct 258 ms 12972 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 13384 KB Output is correct
2 Correct 271 ms 13140 KB Output is correct
3 Correct 504 ms 12972 KB Output is correct
4 Correct 371 ms 12972 KB Output is correct
5 Correct 361 ms 13224 KB Output is correct
6 Correct 246 ms 13372 KB Output is correct
7 Correct 245 ms 12972 KB Output is correct
8 Correct 4 ms 12884 KB Output is correct
9 Correct 5 ms 13060 KB Output is correct
10 Correct 4 ms 13060 KB Output is correct
11 Correct 356 ms 12972 KB Output is correct
12 Correct 287 ms 13112 KB Output is correct
13 Correct 287 ms 13172 KB Output is correct
14 Correct 308 ms 12976 KB Output is correct
15 Correct 31 ms 13112 KB Output is correct
16 Correct 43 ms 13120 KB Output is correct
17 Correct 62 ms 13196 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 12972 KB Output is correct
2 Correct 419 ms 12972 KB Output is correct
3 Correct 399 ms 12972 KB Output is correct
4 Correct 4 ms 13056 KB Output is correct
5 Correct 5 ms 13060 KB Output is correct
6 Correct 4 ms 13060 KB Output is correct
7 Correct 384 ms 13012 KB Output is correct
8 Correct 574 ms 12972 KB Output is correct
9 Correct 442 ms 12972 KB Output is correct
10 Correct 402 ms 12972 KB Output is correct
11 Correct 6 ms 13056 KB Output is correct
12 Correct 6 ms 13060 KB Output is correct
13 Correct 6 ms 13056 KB Output is correct
14 Correct 5 ms 13060 KB Output is correct
15 Correct 4 ms 13052 KB Output is correct
16 Correct 309 ms 12968 KB Output is correct
17 Correct 300 ms 12972 KB Output is correct
18 Correct 299 ms 12972 KB Output is correct
19 Correct 315 ms 12976 KB Output is correct
20 Correct 343 ms 12972 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 13228 KB Output is correct
2 Correct 269 ms 13132 KB Output is correct
3 Correct 498 ms 12972 KB Output is correct
4 Correct 427 ms 12972 KB Output is correct
5 Correct 380 ms 12972 KB Output is correct
6 Correct 273 ms 13136 KB Output is correct
7 Correct 317 ms 12972 KB Output is correct
8 Correct 5 ms 13060 KB Output is correct
9 Correct 6 ms 13060 KB Output is correct
10 Correct 4 ms 13056 KB Output is correct
11 Correct 273 ms 13080 KB Output is correct
12 Correct 320 ms 13056 KB Output is correct
13 Correct 544 ms 12972 KB Output is correct
14 Correct 489 ms 12972 KB Output is correct
15 Correct 363 ms 12972 KB Output is correct
16 Correct 250 ms 12972 KB Output is correct
17 Correct 344 ms 12972 KB Output is correct
18 Correct 260 ms 13140 KB Output is correct
19 Correct 254 ms 13420 KB Output is correct
20 Correct 280 ms 12972 KB Output is correct
21 Correct 34 ms 13116 KB Output is correct
22 Correct 42 ms 13388 KB Output is correct
23 Correct 61 ms 13340 KB Output is correct
24 Correct 6 ms 13060 KB Output is correct
25 Correct 6 ms 13048 KB Output is correct
26 Correct 6 ms 13060 KB Output is correct
27 Correct 5 ms 13056 KB Output is correct
28 Correct 4 ms 13060 KB Output is correct
29 Correct 298 ms 12972 KB Output is correct
30 Correct 292 ms 12972 KB Output is correct
31 Correct 325 ms 12972 KB Output is correct
32 Correct 293 ms 12972 KB Output is correct
33 Correct 306 ms 12972 KB Output is correct
34 Correct 199 ms 13112 KB Output is correct
35 Correct 303 ms 13652 KB Output is correct
36 Correct 273 ms 13368 KB Output is correct
37 Correct 275 ms 13152 KB Output is correct
38 Correct 246 ms 13152 KB Output is correct
39 Correct 266 ms 13360 KB Output is correct
40 Correct 306 ms 13396 KB Output is correct
41 Correct 253 ms 13364 KB Output is correct
42 Correct 39 ms 13104 KB Output is correct
43 Correct 57 ms 12944 KB Output is correct
44 Correct 81 ms 13216 KB Output is correct
45 Correct 112 ms 13108 KB Output is correct
46 Correct 184 ms 13072 KB Output is correct
47 Correct 193 ms 13104 KB Output is correct
48 Correct 39 ms 13724 KB Output is correct
49 Correct 44 ms 13964 KB Output is correct