oj.uz

Submission #321871

# Submission time Handle Problem Language Result Execution time Memory
321871 2020-11-13T13:26:13 Z akobi Stations (IOI20_stations) C++14
100 / 100
 1097 ms 1248 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
    vector< vector<int> > edge;
    vector<int> t,p,fix,anss;
    vector< pair<int,int> >ans;
    for (int i=0; i<n; i++)
    {
        edge.pb(t);
        p.pb(0);
        fix.pb(0);
        anss.pb(0);
    }
    for (int i=0; i<n-1; i++)
    {
        edge[u[i]].pb(v[i]);
        edge[v[i]].pb(u[i]);
    }
    p[0]=-1;
    int c=0,cnt=0,l=0;
    while (c>=0)
    {
        int inn=0,out=0,bbb=0;
        if (fix[c]==0)
        {
            inn=cnt++;
            if (!l)
            {
                ans.pb(mp(inn,c));
                // cout<<inn<<" "<<c<<endl;
            } 
        }
        fix[c]=1;
        for (int i=0; i<(int)(edge[c].size()); i++)
        {
            if (edge[c][i]!=p[c] && fix[ edge[c][i] ]==0)
            {
                p[ edge[c][i] ]=c;
                c=edge[c][i];
                bbb=1;
                break;
            }
        }
        if (bbb)
        {
            l=(l+1)%2;
            continue;
        }
        out=cnt++;
        if (l)
        {
            ans.pb(mp(out,c));
            // cout<<out<<" "<<c<<endl;
        }
        c=p[c];
        l=(l+1)%2;
    }
    sort(ans.begin(),ans.end());
    for (int i=0; i<n; i++)
        anss[ans[i].S]=i;
    return anss;
}
int find_next_station(int s, int t, vector<int> c)
{
    if (s<c[0])
    {
        //in
        if (t<s || t>c[c.size()-2])
            return c[c.size()-1];
        for (int i=0; i<(int)(c.size())-1; i++)
            if (t<=c[i])
                return c[i];
    }
    else
    {
        //out
        if (t>s || t<c[1])
            return c[0];
        for (int i=1; i<(int)(c.size())-1; i++)
            if (t<c[i+1])
                return c[i];
        return c[c.size()-1];
    }
    return -1;
}
// int n,k,a,b;
// vector<int> u,v,ans;
// int main()
// {
//     cin>>n>>k;
//     for (int i=0; i<n-1; i++)
//     {
//         cin>>a>>b;
//         u.pb(a);
//         v.pb(b);
//     }
//     ans=label(n,k,u,v);
//     for (int i=0; i<n; i++)
//         cout<<ans[i]<<" ";
//     cout<<endl;
//     return 0;
// }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 756 KB Output is correct
2 Correct 464 ms 884 KB Output is correct
3 Correct 996 ms 868 KB Output is correct
4 Correct 629 ms 868 KB Output is correct
5 Correct 602 ms 660 KB Output is correct
6 Correct 522 ms 756 KB Output is correct
7 Correct 543 ms 756 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 1 ms 736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 764 KB Output is correct
2 Correct 624 ms 768 KB Output is correct
3 Correct 934 ms 868 KB Output is correct
4 Correct 723 ms 876 KB Output is correct
5 Correct 687 ms 756 KB Output is correct
6 Correct 535 ms 756 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 756 KB Output is correct
2 Correct 461 ms 884 KB Output is correct
3 Correct 857 ms 868 KB Output is correct
4 Correct 760 ms 876 KB Output is correct
5 Correct 734 ms 868 KB Output is correct
6 Correct 460 ms 884 KB Output is correct
7 Correct 443 ms 768 KB Output is correct
8 Correct 2 ms 868 KB Output is correct
9 Correct 4 ms 756 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 782 ms 756 KB Output is correct
12 Correct 581 ms 976 KB Output is correct
13 Correct 480 ms 864 KB Output is correct
14 Correct 443 ms 768 KB Output is correct
15 Correct 55 ms 736 KB Output is correct
16 Correct 74 ms 772 KB Output is correct
17 Correct 105 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 955 ms 736 KB Output is correct
2 Correct 661 ms 756 KB Output is correct
3 Correct 651 ms 632 KB Output is correct
4 Correct 3 ms 1004 KB Output is correct
5 Correct 5 ms 884 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 691 ms 800 KB Output is correct
8 Correct 1097 ms 760 KB Output is correct
9 Correct 828 ms 868 KB Output is correct
10 Correct 757 ms 868 KB Output is correct
11 Correct 6 ms 868 KB Output is correct
12 Correct 7 ms 756 KB Output is correct
13 Correct 6 ms 876 KB Output is correct
14 Correct 3 ms 756 KB Output is correct
15 Correct 2 ms 736 KB Output is correct
16 Correct 633 ms 736 KB Output is correct
17 Correct 506 ms 876 KB Output is correct
18 Correct 508 ms 896 KB Output is correct
19 Correct 522 ms 868 KB Output is correct
20 Correct 496 ms 868 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 756 KB Output is correct
2 Correct 457 ms 884 KB Output is correct
3 Correct 1063 ms 660 KB Output is correct
4 Correct 677 ms 756 KB Output is correct
5 Correct 609 ms 868 KB Output is correct
6 Correct 452 ms 756 KB Output is correct
7 Correct 533 ms 884 KB Output is correct
8 Correct 3 ms 736 KB Output is correct
9 Correct 4 ms 736 KB Output is correct
10 Correct 1 ms 756 KB Output is correct
11 Correct 541 ms 764 KB Output is correct
12 Correct 694 ms 756 KB Output is correct
13 Correct 919 ms 868 KB Output is correct
14 Correct 741 ms 756 KB Output is correct
15 Correct 661 ms 1004 KB Output is correct
16 Correct 489 ms 756 KB Output is correct
17 Correct 598 ms 876 KB Output is correct
18 Correct 486 ms 864 KB Output is correct
19 Correct 524 ms 864 KB Output is correct
20 Correct 462 ms 768 KB Output is correct
21 Correct 57 ms 848 KB Output is correct
22 Correct 73 ms 884 KB Output is correct
23 Correct 111 ms 1044 KB Output is correct
24 Correct 6 ms 876 KB Output is correct
25 Correct 5 ms 756 KB Output is correct
26 Correct 4 ms 876 KB Output is correct
27 Correct 4 ms 736 KB Output is correct
28 Correct 2 ms 868 KB Output is correct
29 Correct 620 ms 736 KB Output is correct
30 Correct 570 ms 1060 KB Output is correct
31 Correct 522 ms 756 KB Output is correct
32 Correct 553 ms 868 KB Output is correct
33 Correct 634 ms 756 KB Output is correct
34 Correct 325 ms 756 KB Output is correct
35 Correct 455 ms 736 KB Output is correct
36 Correct 453 ms 1004 KB Output is correct
37 Correct 483 ms 864 KB Output is correct
38 Correct 612 ms 992 KB Output is correct
39 Correct 520 ms 864 KB Output is correct
40 Correct 422 ms 856 KB Output is correct
41 Correct 455 ms 1248 KB Output is correct
42 Correct 74 ms 736 KB Output is correct
43 Correct 132 ms 756 KB Output is correct
44 Correct 170 ms 1004 KB Output is correct
45 Correct 188 ms 1000 KB Output is correct
46 Correct 369 ms 756 KB Output is correct
47 Correct 295 ms 884 KB Output is correct
48 Correct 68 ms 1000 KB Output is correct
49 Correct 57 ms 864 KB Output is correct