oj.uz

Submission #316197

# Submission time Handle Problem Language Result Execution time Memory
316197 2020-10-25T16:57:15 Z ScarletS Stations (IOI20_stations) C++17
100 / 100
 964 ms 1336 KB 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;

const int maxn = 1e3;
int tin[maxn],tout[maxn],t;
vector<int> edges[maxn];
vector<pii> temp;

void dfs(int c, int p, bool h)
{
    tin[c]=++t;
    for (int i : edges[c])
        if (i!=p)
            dfs(i,c,h^1);
    tout[c]=++t;
    if (h)
        temp.push_back({tout[c],c});
    else
        temp.push_back({tin[c],c});
}

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
    vector<int> labels(n);
    for (int i=0;i<n;++i)
        edges[i].clear();
    for (int i=0;i<n-1;++i)
    {
        edges[u[i]].push_back(v[i]);
        edges[v[i]].push_back(u[i]);
    }
    temp.clear();
    t=-1;
    dfs(0,-1,0);
    sort(temp.begin(), temp.end());
    for (int i=0;i<n;++i)
        labels[temp[i].s]=i;
    return labels;
}

int find_next_station(int a, int b, vector<int> c)
{
    int x = c.size();
    vector<pii> v;
    sort(c.begin(), c.end());
    if (a==0)
    {
        v.push_back({1,c[0]});
        for (int i=1;i<x;++i)
            v.push_back({c[i-1]+1,c[i]});
        for (pii i : v)
            if (i.f<=b&&b<=i.s)
                return i.s;
        while (1)
            ++a;
    }
    if (a<c[0])
    {
        if (x>1)
        {
            v.push_back({a+1,c[0]});
            if (a+1<=b&&b<=c[0])
                return c[0];
            for (int i=1;i<x-1;++i)
                if (c[i-1]+1<=b&&b<=c[i])
                    return c[i];
        }
        return c.back();
    }
    if (x>1)
    {
        if (c[x-1]<=b&&b<=a-1)
            return c[x-1];
        for (int i=x-2;i>=0;--i)
            if (c[i]<=b&&b<=c[i+1]-1)
                return c[i];
    }
    return c[0];
}
/**
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    return 0;
}
**/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 1336 KB Output is correct
2 Correct 478 ms 1024 KB Output is correct
3 Correct 887 ms 768 KB Output is correct
4 Correct 669 ms 876 KB Output is correct
5 Correct 588 ms 768 KB Output is correct
6 Correct 456 ms 1024 KB Output is correct
7 Correct 462 ms 1024 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 876 KB Output is correct
10 Correct 2 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 928 KB Output is correct
2 Correct 555 ms 808 KB Output is correct
3 Correct 874 ms 768 KB Output is correct
4 Correct 659 ms 876 KB Output is correct
5 Correct 621 ms 768 KB Output is correct
6 Correct 445 ms 812 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 1016 KB Output is correct
2 Correct 461 ms 1024 KB Output is correct
3 Correct 864 ms 876 KB Output is correct
4 Correct 646 ms 768 KB Output is correct
5 Correct 591 ms 908 KB Output is correct
6 Correct 473 ms 1024 KB Output is correct
7 Correct 442 ms 1008 KB Output is correct
8 Correct 3 ms 1012 KB Output is correct
9 Correct 4 ms 872 KB Output is correct
10 Correct 1 ms 884 KB Output is correct
11 Correct 596 ms 1024 KB Output is correct
12 Correct 477 ms 1088 KB Output is correct
13 Correct 466 ms 1100 KB Output is correct
14 Correct 449 ms 768 KB Output is correct
15 Correct 56 ms 868 KB Output is correct
16 Correct 71 ms 896 KB Output is correct
17 Correct 109 ms 928 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 892 ms 872 KB Output is correct
2 Correct 652 ms 876 KB Output is correct
3 Correct 590 ms 768 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 624 ms 768 KB Output is correct
8 Correct 853 ms 768 KB Output is correct
9 Correct 677 ms 868 KB Output is correct
10 Correct 589 ms 884 KB Output is correct
11 Correct 6 ms 880 KB Output is correct
12 Correct 5 ms 880 KB Output is correct
13 Correct 6 ms 884 KB Output is correct
14 Correct 3 ms 876 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 505 ms 1004 KB Output is correct
17 Correct 508 ms 868 KB Output is correct
18 Correct 510 ms 768 KB Output is correct
19 Correct 511 ms 872 KB Output is correct
20 Correct 541 ms 768 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 1024 KB Output is correct
2 Correct 539 ms 1024 KB Output is correct
3 Correct 898 ms 876 KB Output is correct
4 Correct 722 ms 876 KB Output is correct
5 Correct 560 ms 876 KB Output is correct
6 Correct 439 ms 1024 KB Output is correct
7 Correct 554 ms 1024 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 501 ms 800 KB Output is correct
12 Correct 572 ms 808 KB Output is correct
13 Correct 964 ms 768 KB Output is correct
14 Correct 837 ms 768 KB Output is correct
15 Correct 696 ms 876 KB Output is correct
16 Correct 565 ms 768 KB Output is correct
17 Correct 687 ms 768 KB Output is correct
18 Correct 508 ms 1008 KB Output is correct
19 Correct 555 ms 1064 KB Output is correct
20 Correct 540 ms 768 KB Output is correct
21 Correct 74 ms 768 KB Output is correct
22 Correct 93 ms 884 KB Output is correct
23 Correct 106 ms 908 KB Output is correct
24 Correct 6 ms 768 KB Output is correct
25 Correct 6 ms 768 KB Output is correct
26 Correct 5 ms 768 KB Output is correct
27 Correct 4 ms 768 KB Output is correct
28 Correct 2 ms 768 KB Output is correct
29 Correct 570 ms 768 KB Output is correct
30 Correct 602 ms 768 KB Output is correct
31 Correct 510 ms 776 KB Output is correct
32 Correct 580 ms 876 KB Output is correct
33 Correct 603 ms 868 KB Output is correct
34 Correct 338 ms 1124 KB Output is correct
35 Correct 502 ms 1024 KB Output is correct
36 Correct 467 ms 1024 KB Output is correct
37 Correct 484 ms 1016 KB Output is correct
38 Correct 511 ms 1140 KB Output is correct
39 Correct 556 ms 1268 KB Output is correct
40 Correct 527 ms 1024 KB Output is correct
41 Correct 513 ms 888 KB Output is correct
42 Correct 72 ms 1196 KB Output is correct
43 Correct 115 ms 896 KB Output is correct
44 Correct 143 ms 764 KB Output is correct
45 Correct 174 ms 780 KB Output is correct
46 Correct 319 ms 796 KB Output is correct
47 Correct 304 ms 1024 KB Output is correct
48 Correct 66 ms 768 KB Output is correct
49 Correct 63 ms 1024 KB Output is correct