oj.uz

Submission #720527

# Submission time Handle Problem Language Result Execution time Memory
720527 2023-04-08T11:59:18 Z bin9638 Stations (IOI20_stations) C++17
100 / 100
 928 ms 1316 KB 
#include <bits/stdc++.h>

#ifndef SKY
#include "stations.h"
#endif // SKY

using namespace std;

#define N 10010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

int n,k,times;
vector<int>g[N],kq;
ii cnt[N],b[N];

void DFS(int u,int p)
{
    cnt[u].fs=++times;
    for(auto v:g[u])
        if(v!=p)
            DFS(v,u);
    cnt[u].sc=++times;
}

void build(int u,int p,int id)
{
    if(id==0)
        kq[u]=cnt[u].fs;
            else kq[u]=cnt[u].sc;
    for(auto v:g[u])
        if(v!=p)
            build(v,u,(id^1));
}

vector<int> label(int dm, int vl, vector<int> canh_fs, vector<int> canh_sc)
{
    n=dm;
    k=vl;
    for(int i=0;i<n;i++)
        g[i].clear();
    kq.resize(n,0);
    times=0;
    for(int i=0;i<n-1;i++)
    {
        int u=canh_fs[i],v=canh_sc[i];
        g[u].pb(v);
        g[v].pb(u);
    }
    DFS(0,-1);
    build(0,-1,0);
    for(int i=0;i<n;i++)
        b[i]={kq[i],i};
    sort(b,b+n);
    for(int i=0;i<n;i++)
        kq[b[i].sc]=i+1;
    return kq;
}

int find_next_station(int u, int v, vector<int> s)
{
    if(s.size()==1)
        return s[0];
    if(u<=*min_element(s.begin(),s.end()))
    {
        sort(s.begin(),s.end());
        if(u+1<=v&&s[0]>=v)
            return s[0];
        for(int i=1;i<(u!=1 ? s.size()-1 : s.size());i++)
            if(s[i-1]+1<=v&&s[i]>=v)
                return s[i];
        return s.back();
    }else
    {
        sort(s.begin(),s.end());
        if(s.back()<=v&&u-1>=v)
            return s.back();
        for(int i=s.size()-2;i>=1;i--)
           if(s[i]<=v&&s[i+1]-1>=v)
                return s[i];
        return s[0];
    }
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,k;
    cin>>n>>k;
    vector<int>u(n-1),v(n-1);
    for(int i=0;i<n-1;i++)
    {
        cin>>u[i]>>v[i];
    }
    vector<int>kq=label(n,k,u,v);
    for(int i=0;i<n;i++)cout<<kq[i]<<" ";cout<<endl;
    int S,T;
    cin>>S>>T;
    vector<int>s;
    for(auto v:g[S])
        s.pb(kq[v]);
    cout<<find_next_station(kq[S],kq[T],s);
    return 0;
}
#endif

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int i=1;i<(u!=1 ? s.size()-1 : s.size());i++)
      |                     ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 1140 KB Output is correct
2 Correct 443 ms 1056 KB Output is correct
3 Correct 855 ms 1004 KB Output is correct
4 Correct 707 ms 1004 KB Output is correct
5 Correct 607 ms 1056 KB Output is correct
6 Correct 475 ms 1060 KB Output is correct
7 Correct 522 ms 1008 KB Output is correct
8 Correct 2 ms 1008 KB Output is correct
9 Correct 5 ms 1008 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 1004 KB Output is correct
2 Correct 555 ms 1000 KB Output is correct
3 Correct 876 ms 928 KB Output is correct
4 Correct 598 ms 932 KB Output is correct
5 Correct 533 ms 1000 KB Output is correct
6 Correct 464 ms 1056 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 1140 KB Output is correct
2 Correct 344 ms 1140 KB Output is correct
3 Correct 857 ms 1000 KB Output is correct
4 Correct 647 ms 996 KB Output is correct
5 Correct 639 ms 928 KB Output is correct
6 Correct 437 ms 1132 KB Output is correct
7 Correct 452 ms 1008 KB Output is correct
8 Correct 2 ms 1008 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 2 ms 1008 KB Output is correct
11 Correct 581 ms 928 KB Output is correct
12 Correct 475 ms 1316 KB Output is correct
13 Correct 396 ms 1128 KB Output is correct
14 Correct 381 ms 1060 KB Output is correct
15 Correct 55 ms 1012 KB Output is correct
16 Correct 65 ms 1056 KB Output is correct
17 Correct 99 ms 1100 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 878 ms 932 KB Output is correct
2 Correct 687 ms 996 KB Output is correct
3 Correct 562 ms 1004 KB Output is correct
4 Correct 3 ms 1008 KB Output is correct
5 Correct 4 ms 1008 KB Output is correct
6 Correct 2 ms 1008 KB Output is correct
7 Correct 600 ms 928 KB Output is correct
8 Correct 843 ms 928 KB Output is correct
9 Correct 605 ms 932 KB Output is correct
10 Correct 593 ms 1000 KB Output is correct
11 Correct 4 ms 928 KB Output is correct
12 Correct 6 ms 1016 KB Output is correct
13 Correct 4 ms 1012 KB Output is correct
14 Correct 2 ms 1008 KB Output is correct
15 Correct 2 ms 1012 KB Output is correct
16 Correct 496 ms 932 KB Output is correct
17 Correct 424 ms 932 KB Output is correct
18 Correct 479 ms 956 KB Output is correct
19 Correct 471 ms 1004 KB Output is correct
20 Correct 469 ms 928 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 1136 KB Output is correct
2 Correct 472 ms 1132 KB Output is correct
3 Correct 928 ms 928 KB Output is correct
4 Correct 669 ms 928 KB Output is correct
5 Correct 616 ms 928 KB Output is correct
6 Correct 378 ms 1056 KB Output is correct
7 Correct 429 ms 1060 KB Output is correct
8 Correct 3 ms 1008 KB Output is correct
9 Correct 5 ms 1008 KB Output is correct
10 Correct 1 ms 1012 KB Output is correct
11 Correct 372 ms 996 KB Output is correct
12 Correct 536 ms 1056 KB Output is correct
13 Correct 751 ms 928 KB Output is correct
14 Correct 725 ms 928 KB Output is correct
15 Correct 557 ms 928 KB Output is correct
16 Correct 378 ms 1008 KB Output is correct
17 Correct 594 ms 932 KB Output is correct
18 Correct 424 ms 1084 KB Output is correct
19 Correct 403 ms 1192 KB Output is correct
20 Correct 424 ms 1008 KB Output is correct
21 Correct 53 ms 1008 KB Output is correct
22 Correct 62 ms 1140 KB Output is correct
23 Correct 93 ms 1056 KB Output is correct
24 Correct 5 ms 1016 KB Output is correct
25 Correct 4 ms 1016 KB Output is correct
26 Correct 4 ms 1016 KB Output is correct
27 Correct 4 ms 1016 KB Output is correct
28 Correct 2 ms 1008 KB Output is correct
29 Correct 501 ms 932 KB Output is correct
30 Correct 521 ms 1004 KB Output is correct
31 Correct 522 ms 928 KB Output is correct
32 Correct 552 ms 928 KB Output is correct
33 Correct 570 ms 928 KB Output is correct
34 Correct 340 ms 1056 KB Output is correct
35 Correct 453 ms 1200 KB Output is correct
36 Correct 404 ms 1048 KB Output is correct
37 Correct 449 ms 1048 KB Output is correct
38 Correct 453 ms 1132 KB Output is correct
39 Correct 361 ms 1132 KB Output is correct
40 Correct 481 ms 1072 KB Output is correct
41 Correct 465 ms 1296 KB Output is correct
42 Correct 62 ms 1060 KB Output is correct
43 Correct 102 ms 1056 KB Output is correct
44 Correct 167 ms 1188 KB Output is correct
45 Correct 172 ms 1120 KB Output is correct
46 Correct 301 ms 1056 KB Output is correct
47 Correct 305 ms 1060 KB Output is correct
48 Correct 41 ms 1060 KB Output is correct
49 Correct 61 ms 1296 KB Output is correct