oj.uz

Submission #828590

# Submission time Handle Problem Language Result Execution time Memory
828590 2023-08-17T12:13:25 Z ALeonidou Stations (IOI20_stations) C++17
100 / 100
 736 ms 876 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

#define ll int
#define F first
#define S second
#define MID ((l+r)/2)
#define sz(x) (ll)x.size()
#define pb push_back
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
typedef vector <ll> vi;
typedef pair<ll,ll> ii;
typedef vector <ii> vii;

void printVct(vi v){
    for (ll i =0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

void printVctPair(vii v){
    for (ll i =0; i<sz(v); i++){
        cout<<"("<<v[i].F<<" "<<v[i].S<<"), ";
    }
    cout<<endl;
}

vector <vi> adj;
vi tin, tout, vis, labels;
ll dfsTimer = 0;
void dfs (ll u, bool parity){
    vis[u] = 1;
    tin[u] = dfsTimer;
    dfsTimer++;
    vis[u] = 1;
    for (ll i=0;i<sz(adj[u]); i++){
        if (!vis[adj[u][i]]){
            dfs(adj[u][i], !parity);
        }
    }
    tout[u] = dfsTimer;
    dfsTimer++;
    if (parity) labels[u] = tout[u];
    else labels[u] = tin[u];
}

vi label(int n, int k, vi u, vi v){
    adj.assign(n, vi());
    for (ll i =0; i<n-1; i++){
        adj[u[i]].pb(v[i]);
        adj[v[i]].pb(u[i]);
    }

    tin.resize(n);
    tout.resize(n);
    vis.assign(n, 0);
    labels.resize(n);

    dfs(0, 0);

    // cout<<"tin: ";
    // printVct(tin);

    // cout<<"tout: ";
    // printVct(tout);

    // cout<<"labels: ";
    // printVct(labels);

    vi labels_order(n);
    for (ll i =0; i<n ;i++) labels_order[i] = i;
    sort(labels_order.begin(), labels_order.end(), [&](ll a, ll b){ return (labels[a] < labels[b]);});

    // cout<<"labels_order: ";
    // printVct(labels_order);

    vi labels_rank(n);
    for (ll i = 0; i<n ;i++){
        labels_rank[labels_order[i]] = i;
    }

    // cout<<"labels_rank: ";
    // printVct(labels_rank);

    return labels_rank;
}

// ll calls = 0;
int find_next_station(int s, int t, vi c) {
    // calls++;
    // cout<<endl<<endl<<"-------"<<calls<<"-------";
    // dbg2(s,t);
    // cout<<"c: "; printVct(c);
    // cout<<endl;

	//STEP 1: Find in or out
    bool isin = (s < c[0]);
    // dbg(isin);

    //STEP 2: Find parent and remove
    ll p;
    sort(c.begin(), c.end());
    if (isin){
        p = c.back();
        c.pop_back();
    }
    else{
        p = c[0];
        c.erase(c.begin());
    }
    // dbg(p);

    //STEP 3: Find Range
    vii ranges;
    if (!isin){
        for (ll i = 0; i<sz(c)-1; i++){
            ranges.pb(ii(c[i], c[i+1]-1));
        }
        ranges.pb(ii(c.back(), s-1));
    }
    else{
        ranges.pb(ii(s+1, c[0]));
        for (ll i = 1; i<sz(c); i++){
            ranges.pb(ii(c[i-1]+1, c[i]));
        }
    }
    // cout<<"ranges: ";
    // printVctPair(ranges);

    //STEP 4: Solve
    ll ans = p;
    for (ll i =0; i<sz(ranges);i++){
        if (t >= ranges[i].F && t <= ranges[i].S){
            ans = c[i];
            break;
        }
    }
    // dbg(ans);

    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 624 KB Output is correct
2 Correct 409 ms 676 KB Output is correct
3 Correct 557 ms 504 KB Output is correct
4 Correct 536 ms 572 KB Output is correct
5 Correct 511 ms 484 KB Output is correct
6 Correct 396 ms 632 KB Output is correct
7 Correct 400 ms 548 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 628 KB Output is correct
2 Correct 493 ms 616 KB Output is correct
3 Correct 736 ms 548 KB Output is correct
4 Correct 491 ms 416 KB Output is correct
5 Correct 428 ms 420 KB Output is correct
6 Correct 372 ms 508 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 672 KB Output is correct
2 Correct 332 ms 804 KB Output is correct
3 Correct 735 ms 416 KB Output is correct
4 Correct 492 ms 496 KB Output is correct
5 Correct 413 ms 504 KB Output is correct
6 Correct 381 ms 644 KB Output is correct
7 Correct 311 ms 632 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 461 ms 508 KB Output is correct
12 Correct 400 ms 632 KB Output is correct
13 Correct 337 ms 876 KB Output is correct
14 Correct 327 ms 508 KB Output is correct
15 Correct 40 ms 444 KB Output is correct
16 Correct 65 ms 612 KB Output is correct
17 Correct 82 ms 504 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 420 KB Output is correct
2 Correct 603 ms 416 KB Output is correct
3 Correct 379 ms 500 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 0 ms 500 KB Output is correct
7 Correct 420 ms 420 KB Output is correct
8 Correct 705 ms 416 KB Output is correct
9 Correct 567 ms 504 KB Output is correct
10 Correct 429 ms 508 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 4 ms 492 KB Output is correct
13 Correct 2 ms 496 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 434 ms 420 KB Output is correct
17 Correct 431 ms 544 KB Output is correct
18 Correct 406 ms 504 KB Output is correct
19 Correct 416 ms 416 KB Output is correct
20 Correct 435 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 676 KB Output is correct
2 Correct 349 ms 648 KB Output is correct
3 Correct 566 ms 420 KB Output is correct
4 Correct 496 ms 508 KB Output is correct
5 Correct 400 ms 500 KB Output is correct
6 Correct 394 ms 548 KB Output is correct
7 Correct 303 ms 548 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 321 ms 640 KB Output is correct
12 Correct 377 ms 504 KB Output is correct
13 Correct 626 ms 416 KB Output is correct
14 Correct 450 ms 420 KB Output is correct
15 Correct 515 ms 416 KB Output is correct
16 Correct 371 ms 580 KB Output is correct
17 Correct 490 ms 416 KB Output is correct
18 Correct 344 ms 620 KB Output is correct
19 Correct 386 ms 636 KB Output is correct
20 Correct 391 ms 504 KB Output is correct
21 Correct 40 ms 500 KB Output is correct
22 Correct 59 ms 544 KB Output is correct
23 Correct 94 ms 504 KB Output is correct
24 Correct 3 ms 492 KB Output is correct
25 Correct 4 ms 500 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Correct 3 ms 492 KB Output is correct
28 Correct 1 ms 492 KB Output is correct
29 Correct 389 ms 508 KB Output is correct
30 Correct 387 ms 504 KB Output is correct
31 Correct 419 ms 504 KB Output is correct
32 Correct 493 ms 416 KB Output is correct
33 Correct 424 ms 504 KB Output is correct
34 Correct 274 ms 672 KB Output is correct
35 Correct 372 ms 784 KB Output is correct
36 Correct 323 ms 784 KB Output is correct
37 Correct 374 ms 596 KB Output is correct
38 Correct 387 ms 724 KB Output is correct
39 Correct 412 ms 640 KB Output is correct
40 Correct 380 ms 716 KB Output is correct
41 Correct 330 ms 580 KB Output is correct
42 Correct 45 ms 624 KB Output is correct
43 Correct 78 ms 544 KB Output is correct
44 Correct 131 ms 512 KB Output is correct
45 Correct 143 ms 640 KB Output is correct
46 Correct 293 ms 524 KB Output is correct
47 Correct 224 ms 612 KB Output is correct
48 Correct 54 ms 600 KB Output is correct
49 Correct 59 ms 748 KB Output is correct