oj.uz

Submission #706466

# Submission time Handle Problem Language Result Execution time Memory
706466 2023-03-06T16:01:45 Z ToroTN Stations (IOI20_stations) C++14
100 / 100
 946 ms 900 KB 
#include<bits/stdc++.h>
using namespace std;
#include "stations.h"
//#include "stub.cpp"
#include <vector>
#define pb push_back
vector<int> adj[1005];
set<int> ss;
map<int,int> mp;
int st[1005],ed[1005],tim=0,lv[1005],pack[1005],cnt;
void dfs(int u,int p)
{
    st[u]=++tim;
    for(auto node:adj[u])
    {
        if(node==p)continue;
        lv[node]=1-lv[u];
        dfs(node,u);
    }
    ed[u]=++tim;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
    for(int i=1;i<=n;i++)adj[i].clear();
    ss.clear();
    mp.clear();
	for (int i = 0; i < n-1; i++) 
    {
        adj[u[i]+1].pb(v[i]+1);
        adj[v[i]+1].pb(u[i]+1);
	}
    lv[1]=0;
    dfs(1,1);
    for(int i=1;i<=n;i++)
    {
        if(lv[i]==0)
        {
            pack[i]=st[i];
        }else
        {
            pack[i]=ed[i];
        }
    }
    for(int i=1;i<=n;i++)ss.insert(pack[i]);
    cnt=0;
    for(auto it=ss.begin();it!=ss.end();it++)
    {
        mp[(*it)]=cnt;
        ++cnt;
    }
    for(int i=1;i<=n;i++)pack[i]=mp[pack[i]];
    labels.clear();
    for(int i=0;i<n;i++)labels.pb(pack[i+1]);
    /*for(int i=1;i<=n;i++)
    {
        printf("%d\n",i);
        for(auto node:adj[i])
        {
            printf("%d ",node);
        }
        printf("\n");
    }*/
    /*for(int i=0;i<labels.size();i++)
    {
        printf("%d ",labels[i]);
    }
    printf("\n");*/
    return labels; 
}

int find_next_station(int s, int t, std::vector<int> c) 
{
    //printf("hk\n");
    //printf("s=%d t=%d\n",s,t);
    //printf("adj\n");
    /*for(auto node:c)
    {
        printf("%d ",node);
    }
    printf("\n");*/
	if(c.size()==1)return c[0];
    sort(c.begin(),c.end());
    for(auto node:c)
    {
        if(node==t)return t;
    }
    if(s>c[0])
    {
        for(int i=1;i<c.size()-1;i++)
        {
            if(t>=c[i]&&t<c[i+1])
            {
                return c[i];
            }
        }
        if(t>=c[c.size()-1]&&t<s)return c[c.size()-1];
        return c[0];
    }else
    {
        if(t<c[0]&&t>s)return c[0];
        for(int i=1;i<c.size()-1;i++)
        {
            if(t>c[i-1]&&t<c[i])
            {
                return c[i];
            }
        }
        return c[c.size()-1];
    }
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 656 KB Output is correct
2 Correct 458 ms 652 KB Output is correct
3 Correct 837 ms 512 KB Output is correct
4 Correct 644 ms 420 KB Output is correct
5 Correct 574 ms 540 KB Output is correct
6 Correct 494 ms 668 KB Output is correct
7 Correct 455 ms 660 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 4 ms 628 KB Output is correct
10 Correct 0 ms 624 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 668 KB Output is correct
2 Correct 548 ms 676 KB Output is correct
3 Correct 946 ms 528 KB Output is correct
4 Correct 667 ms 544 KB Output is correct
5 Correct 647 ms 416 KB Output is correct
6 Correct 468 ms 660 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 764 KB Output is correct
2 Correct 464 ms 668 KB Output is correct
3 Correct 895 ms 532 KB Output is correct
4 Correct 710 ms 548 KB Output is correct
5 Correct 593 ms 528 KB Output is correct
6 Correct 424 ms 668 KB Output is correct
7 Correct 431 ms 640 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 570 ms 572 KB Output is correct
12 Correct 408 ms 800 KB Output is correct
13 Correct 502 ms 780 KB Output is correct
14 Correct 447 ms 836 KB Output is correct
15 Correct 51 ms 600 KB Output is correct
16 Correct 67 ms 704 KB Output is correct
17 Correct 116 ms 800 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 792 ms 512 KB Output is correct
2 Correct 652 ms 524 KB Output is correct
3 Correct 644 ms 548 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 3 ms 628 KB Output is correct
6 Correct 0 ms 620 KB Output is correct
7 Correct 613 ms 532 KB Output is correct
8 Correct 918 ms 516 KB Output is correct
9 Correct 761 ms 532 KB Output is correct
10 Correct 554 ms 532 KB Output is correct
11 Correct 4 ms 620 KB Output is correct
12 Correct 5 ms 620 KB Output is correct
13 Correct 4 ms 628 KB Output is correct
14 Correct 1 ms 632 KB Output is correct
15 Correct 1 ms 620 KB Output is correct
16 Correct 454 ms 548 KB Output is correct
17 Correct 490 ms 536 KB Output is correct
18 Correct 467 ms 532 KB Output is correct
19 Correct 501 ms 552 KB Output is correct
20 Correct 557 ms 532 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 672 KB Output is correct
2 Correct 444 ms 660 KB Output is correct
3 Correct 939 ms 416 KB Output is correct
4 Correct 653 ms 528 KB Output is correct
5 Correct 644 ms 600 KB Output is correct
6 Correct 448 ms 700 KB Output is correct
7 Correct 561 ms 724 KB Output is correct
8 Correct 1 ms 496 KB Output is correct
9 Correct 5 ms 600 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 441 ms 676 KB Output is correct
12 Correct 536 ms 672 KB Output is correct
13 Correct 877 ms 516 KB Output is correct
14 Correct 674 ms 536 KB Output is correct
15 Correct 517 ms 544 KB Output is correct
16 Correct 465 ms 652 KB Output is correct
17 Correct 535 ms 540 KB Output is correct
18 Correct 481 ms 776 KB Output is correct
19 Correct 417 ms 764 KB Output is correct
20 Correct 446 ms 664 KB Output is correct
21 Correct 47 ms 596 KB Output is correct
22 Correct 66 ms 572 KB Output is correct
23 Correct 101 ms 836 KB Output is correct
24 Correct 6 ms 488 KB Output is correct
25 Correct 4 ms 620 KB Output is correct
26 Correct 3 ms 620 KB Output is correct
27 Correct 4 ms 628 KB Output is correct
28 Correct 2 ms 616 KB Output is correct
29 Correct 485 ms 532 KB Output is correct
30 Correct 538 ms 420 KB Output is correct
31 Correct 572 ms 548 KB Output is correct
32 Correct 483 ms 552 KB Output is correct
33 Correct 535 ms 544 KB Output is correct
34 Correct 356 ms 672 KB Output is correct
35 Correct 353 ms 780 KB Output is correct
36 Correct 482 ms 656 KB Output is correct
37 Correct 444 ms 776 KB Output is correct
38 Correct 489 ms 784 KB Output is correct
39 Correct 359 ms 796 KB Output is correct
40 Correct 442 ms 900 KB Output is correct
41 Correct 459 ms 884 KB Output is correct
42 Correct 46 ms 548 KB Output is correct
43 Correct 99 ms 800 KB Output is correct
44 Correct 123 ms 676 KB Output is correct
45 Correct 175 ms 660 KB Output is correct
46 Correct 325 ms 668 KB Output is correct
47 Correct 300 ms 668 KB Output is correct
48 Correct 77 ms 868 KB Output is correct
49 Correct 59 ms 812 KB Output is correct