oj.uz

Submission #985503

# Submission time Handle Problem Language Result Execution time Memory
985503 2024-05-18T02:00:09 Z Alex0x0 Stations (IOI20_stations) C++14
52.3244 / 100
 622 ms 1512 KB 
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define f first
#define s second
#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)
#define pb push_back
#define all(s) begin(s), end(s)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(s) int(s.size())
#define ENDL '\n'
using namespace std;
typedef long double ld;
typedef int lli;
typedef pair<lli,lli> ii;
typedef vector<lli> vi;
typedef vector<ii> vii;
#define deb(x) cout << #x": " << (x) << endl;

const lli INF = 1e9 + 12;
const lli N = 1e3 + 12;

vector <vi> adj;

vi tk;
lli curVis = 0;
lli id = 0;
lli vis[N];

lli dfs(lli u){
  // cout << u << ' ';
  vis[u] = curVis;
  lli cc = 0;
  lli a = INF, b = -INF;
  for (auto &i : adj[u]){
    if (vis[i] == curVis) continue;
    cc++;
    lli x = dfs(i);
    a = min(a, x % 1000);
    b = max(b, lli(x / 1000ll));
  }
  a = min(a, id);
  b = max(b, id);
  id++;
  // cout << a << ' ' << b << ENDL;
  tk[u] = (1000ll * b) + a;
  return tk[u];
}

vi label(lli n, lli k, vi u, vi v){
  adj.resize(n + 5);
  for (auto &i : adj) i.clear();
  tk.resize(n);
  for (auto &i : tk) i = -1ll;
  id = 0;
  fore(i,0,n-1){
    adj[u[i]].pb(v[i]);
    adj[v[i]].pb(u[i]);
  }
  ++curVis;
  dfs(0);
  // cout << ENDL;
  return tk;
}


lli find_next_station(lli s, lli t, vi c){
  lli l = s % 1000;
  lli r = lli(s / 1000ll);
  lli ll = t % 1000;
  lli rr = lli(t / 1000ll);
  lli father;
  for (auto & i : c){
    lli a = i % 1000;
    lli b = lli(i / 1000ll);
    if (a <= l && r <= b) father = i;
  }
  lli ans = father;
  for (auto & i : c){
    if (i == father) continue;
    lli a = i % 1000;
    lli b = lli(i / 1000ll);
    if (a <= ll && rr <= b) ans = i;
  }
  return ans;
}

// int main(){ _
//   // freopen("file.in","r",stdin);
//   // freopen("file.out","w",stdout);
//   vector<vi> vv;
//   lli t; cin >> t;
//   while (t--){
//     lli n, k; cin >> n >> k;
//     vi a(n-1); vi b(n-1);
//     fore(i,0,n-1) cin >> a[i] >> b[i];
//     vi v = label(n, k, a, b);
//     for (auto & i : v) cout << i << ' '; cout << ENDL;
//     vv.pb(v);
//   }
//   return 0;
// }

Compilation message

stations.cpp: In function 'lli find_next_station(lli, lli, vi)':
stations.cpp:85:10: warning: 'father' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |   return ans;
      |          ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 744 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=9000
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 800 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=995000
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 964 KB Output is correct
2 Correct 288 ms 952 KB Output is correct
3 Correct 622 ms 856 KB Output is correct
4 Correct 461 ms 936 KB Output is correct
5 Correct 371 ms 684 KB Output is correct
6 Correct 301 ms 920 KB Output is correct
7 Correct 283 ms 684 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 375 ms 684 KB Output is correct
12 Correct 300 ms 1184 KB Output is correct
13 Correct 292 ms 1332 KB Output is correct
14 Correct 304 ms 684 KB Output is correct
15 Correct 34 ms 684 KB Output is correct
16 Correct 38 ms 916 KB Output is correct
17 Correct 67 ms 1028 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 684 KB Output is correct
2 Correct 435 ms 684 KB Output is correct
3 Correct 374 ms 684 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 369 ms 684 KB Output is correct
8 Correct 559 ms 684 KB Output is correct
9 Correct 427 ms 684 KB Output is correct
10 Correct 378 ms 684 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 3 ms 764 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 313 ms 684 KB Output is correct
17 Correct 352 ms 684 KB Output is correct
18 Correct 338 ms 684 KB Output is correct
19 Correct 383 ms 684 KB Output is correct
20 Correct 308 ms 684 KB Output is correct

Subtask #5
26.3244 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 344 ms 1140 KB Partially correct
2 Partially correct 308 ms 936 KB Partially correct
3 Correct 559 ms 684 KB Output is correct
4 Partially correct 437 ms 684 KB Partially correct
5 Partially correct 367 ms 684 KB Partially correct
6 Partially correct 300 ms 928 KB Partially correct
7 Partially correct 296 ms 684 KB Partially correct
8 Partially correct 1 ms 764 KB Partially correct
9 Partially correct 3 ms 768 KB Partially correct
10 Partially correct 1 ms 768 KB Partially correct
11 Partially correct 272 ms 888 KB Partially correct
12 Partially correct 347 ms 1000 KB Partially correct
13 Correct 548 ms 684 KB Output is correct
14 Partially correct 445 ms 684 KB Partially correct
15 Partially correct 371 ms 684 KB Partially correct
16 Partially correct 282 ms 684 KB Partially correct
17 Partially correct 345 ms 684 KB Partially correct
18 Partially correct 286 ms 1152 KB Partially correct
19 Partially correct 301 ms 1512 KB Partially correct
20 Partially correct 307 ms 684 KB Partially correct
21 Partially correct 41 ms 764 KB Partially correct
22 Partially correct 43 ms 1164 KB Partially correct
23 Partially correct 59 ms 956 KB Partially correct
24 Partially correct 2 ms 768 KB Partially correct
25 Partially correct 3 ms 768 KB Partially correct
26 Partially correct 2 ms 768 KB Partially correct
27 Partially correct 1 ms 772 KB Partially correct
28 Partially correct 1 ms 764 KB Partially correct
29 Partially correct 307 ms 684 KB Partially correct
30 Partially correct 330 ms 684 KB Partially correct
31 Partially correct 337 ms 864 KB Partially correct
32 Partially correct 318 ms 684 KB Partially correct
33 Partially correct 280 ms 684 KB Partially correct
34 Partially correct 194 ms 940 KB Partially correct
35 Partially correct 282 ms 1180 KB Partially correct
36 Partially correct 269 ms 1028 KB Partially correct
37 Partially correct 284 ms 1168 KB Partially correct
38 Partially correct 296 ms 1080 KB Partially correct
39 Partially correct 271 ms 1000 KB Partially correct
40 Partially correct 270 ms 1012 KB Partially correct
41 Partially correct 273 ms 1156 KB Partially correct
42 Partially correct 35 ms 940 KB Partially correct
43 Partially correct 65 ms 892 KB Partially correct
44 Partially correct 90 ms 916 KB Partially correct
45 Partially correct 87 ms 956 KB Partially correct
46 Partially correct 196 ms 860 KB Partially correct
47 Partially correct 199 ms 892 KB Partially correct
48 Partially correct 33 ms 1172 KB Partially correct
49 Partially correct 36 ms 948 KB Partially correct