oj.uz

Submission #364786

# Submission time Handle Problem Language Result Execution time Memory
364786 2021-02-10T03:29:50 Z leinad2 Stations (IOI20_stations) C++17
52.3205 / 100
 1101 ms 1364 KB 
#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[1010];
int in[1010], out[1010], cnt, vis[1010];
void dfs(int v)
{
    in[v]=++cnt;
    for(int i=0;i<adj[v].size();i++)
    {
        int p=adj[v][i];
        if(!vis[p])
        {
            vis[p]=1;
            dfs(p);
        }
    }
    out[v]=cnt;
}
vector<int>label(int n, int k, vector<int>u, vector<int>v)
{
	vis[0]=1;
  for(int i=1;i<n;i++)vis[i]=0;
  cnt=0;
  for(int i=0;i<n;i++)in[i]=out[i]=0,adj[i].clear();
	for(int i=0;i<u.size();i++)
    {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    dfs(0);
    vector<int>ans;
    for(int i=0;i<n;i++)ans.push_back(in[i]*1000+out[i]-1001);
    return ans;
}
int find_next_station(int s, int t, vector<int>c)
{
    int aa=s/1000;
    int bb=s%1000;
    int cc=t/1000;
    int dd=t%1000;
    if(cc<=aa&&bb<=dd||bb<cc||dd<aa)
    {
        for(int i=0;i<c.size();i++)
        {
            int ee=c[i]/1000;
            int ff=c[i]%1000;
            if(ee<=aa&&bb<=ff)return c[i];
        }
    }
    for(int i=0;i<c.size();i++)
    {
        int ee=c[i]/1000;
        int ff=c[i]%1000;
        if(ee<=cc&&dd<=ff&&!(ee<=aa&&bb<=ff))return c[i];
    }
}

Compilation message

stations.cpp: In function 'void dfs(int)':
stations.cpp:9:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i=0;i<u.size();i++)
      |              ~^~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:42:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |     if(cc<=aa&&bb<=dd||bb<cc||dd<aa)
      |        ~~~~~~^~~~~~~~
stations.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i=0;i<c.size();i++)
      |                     ~^~~~~~~~~
stations.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0;i<c.size();i++)
      |                 ~^~~~~~~~~
stations.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 492 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=6009
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 364 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1511
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 1092 KB Output is correct
2 Correct 445 ms 1120 KB Output is correct
3 Correct 1061 ms 940 KB Output is correct
4 Correct 669 ms 948 KB Output is correct
5 Correct 630 ms 940 KB Output is correct
6 Correct 655 ms 1228 KB Output is correct
7 Correct 608 ms 992 KB Output is correct
8 Correct 3 ms 864 KB Output is correct
9 Correct 6 ms 864 KB Output is correct
10 Correct 2 ms 864 KB Output is correct
11 Correct 702 ms 940 KB Output is correct
12 Correct 572 ms 1120 KB Output is correct
13 Correct 537 ms 1352 KB Output is correct
14 Correct 524 ms 864 KB Output is correct
15 Correct 54 ms 932 KB Output is correct
16 Correct 93 ms 864 KB Output is correct
17 Correct 126 ms 872 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 1104 KB Output is correct
2 Correct 784 ms 864 KB Output is correct
3 Correct 641 ms 832 KB Output is correct
4 Correct 5 ms 940 KB Output is correct
5 Correct 6 ms 736 KB Output is correct
6 Correct 2 ms 776 KB Output is correct
7 Correct 773 ms 884 KB Output is correct
8 Correct 1022 ms 1084 KB Output is correct
9 Correct 744 ms 940 KB Output is correct
10 Correct 620 ms 772 KB Output is correct
11 Correct 6 ms 948 KB Output is correct
12 Correct 7 ms 904 KB Output is correct
13 Correct 6 ms 864 KB Output is correct
14 Correct 5 ms 736 KB Output is correct
15 Correct 2 ms 864 KB Output is correct
16 Correct 563 ms 736 KB Output is correct
17 Correct 643 ms 736 KB Output is correct
18 Correct 536 ms 864 KB Output is correct
19 Correct 537 ms 940 KB Output is correct
20 Correct 424 ms 864 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 621 ms 992 KB Partially correct
2 Partially correct 488 ms 992 KB Partially correct
3 Partially correct 1101 ms 864 KB Partially correct
4 Partially correct 670 ms 864 KB Partially correct
5 Partially correct 628 ms 992 KB Partially correct
6 Partially correct 495 ms 992 KB Partially correct
7 Partially correct 443 ms 868 KB Partially correct
8 Partially correct 3 ms 736 KB Partially correct
9 Partially correct 5 ms 948 KB Partially correct
10 Partially correct 2 ms 948 KB Partially correct
11 Partially correct 511 ms 736 KB Partially correct
12 Partially correct 537 ms 864 KB Partially correct
13 Partially correct 889 ms 940 KB Partially correct
14 Partially correct 727 ms 864 KB Partially correct
15 Partially correct 643 ms 864 KB Partially correct
16 Partially correct 437 ms 736 KB Partially correct
17 Partially correct 539 ms 864 KB Partially correct
18 Partially correct 463 ms 1364 KB Partially correct
19 Partially correct 502 ms 1120 KB Partially correct
20 Partially correct 504 ms 888 KB Partially correct
21 Partially correct 68 ms 932 KB Partially correct
22 Partially correct 69 ms 736 KB Partially correct
23 Partially correct 117 ms 736 KB Partially correct
24 Partially correct 5 ms 736 KB Partially correct
25 Partially correct 8 ms 864 KB Partially correct
26 Partially correct 4 ms 736 KB Partially correct
27 Partially correct 4 ms 864 KB Partially correct
28 Partially correct 2 ms 736 KB Partially correct
29 Partially correct 623 ms 940 KB Partially correct
30 Partially correct 607 ms 864 KB Partially correct
31 Partially correct 483 ms 1068 KB Partially correct
32 Partially correct 477 ms 940 KB Partially correct
33 Partially correct 491 ms 940 KB Partially correct
34 Partially correct 352 ms 992 KB Partially correct
35 Partially correct 398 ms 1084 KB Partially correct
36 Partially correct 447 ms 1224 KB Partially correct
37 Partially correct 446 ms 992 KB Partially correct
38 Partially correct 465 ms 1120 KB Partially correct
39 Partially correct 443 ms 944 KB Partially correct
40 Partially correct 461 ms 992 KB Partially correct
41 Partially correct 481 ms 1236 KB Partially correct
42 Partially correct 63 ms 888 KB Partially correct
43 Partially correct 114 ms 864 KB Partially correct
44 Partially correct 124 ms 992 KB Partially correct
45 Partially correct 158 ms 864 KB Partially correct
46 Partially correct 291 ms 864 KB Partially correct
47 Partially correct 303 ms 868 KB Partially correct
48 Partially correct 74 ms 1012 KB Partially correct
49 Partially correct 63 ms 864 KB Partially correct