oj.uz

Submission #307648

# Submission time Handle Problem Language Result Execution time Memory
307648 2020-09-28T23:38:04 Z azberjibiou Stations (IOI20_stations) C++17
100 / 100
 1199 ms 10688 KB 
#include "stations.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
#define pii pair<int, int>
using namespace std;
const int mxN=100010;
int N;
vector <int> v[mxN], down[mxN];
int ans[mxN];
bool Chk[mxN];
int typ[mxN];
int sub[mxN];
void dfs1(int num, int typn)
{
    Chk[num]=true;
    typ[num]=typn;
    for(int ele : v[num])
    {
        if(Chk[ele])    continue;
        dfs1(ele, 1-typn);
        sub[num]+=sub[ele];
        down[num].push_back(ele);
    }
}
void dfs2(int num, int str, int fin)
{
    if(typ[num]==0) ans[num]=str++;
    else    ans[num]=fin--;
    for(int ele : down[num])
    {
        dfs2(ele, str, str+sub[ele]-1);
        str+=sub[ele];
    }
}
std::vector<int> label(int n, int k, std::vector<int> a, std::vector<int> b) {
	vector<int> labels(n);
	N=n;
	for(int i=0;i<N;i++)    v[i].clear(), down[i].clear();
	for(int i=0;i<N;i++)    Chk[i]=false, typ[i]=0, sub[i]=1, ans[i]=-1;
	for(int i=0;i<N-1;i++)
    {
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    dfs1(1, 0);
    dfs2(1, 0, N-1);
	for (int i = 0; i < n; i++) {
		labels[i] = ans[i];
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	if(c.size()==1) return c[0];
	if(s<c[0])
    {
        int str=s;
        for(int i=0;i<c.size()-1;i++)
        {
            if(str<=t && t<=c[i])   return c[i];
            str=c[i]+1;
        }
        return c.back();
    }
	else
    {
        int fin=s;
        for(int i=c.size()-1;i>0;i--)
        {
            if(t<=fin && t>=c[i])   return c[i];
            fin=c[i]-1;
        }
        return c[0];
    }
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 10480 KB Output is correct
2 Correct 532 ms 10480 KB Output is correct
3 Correct 906 ms 10156 KB Output is correct
4 Correct 668 ms 10280 KB Output is correct
5 Correct 664 ms 10148 KB Output is correct
6 Correct 479 ms 10480 KB Output is correct
7 Correct 584 ms 10268 KB Output is correct
8 Correct 8 ms 10112 KB Output is correct
9 Correct 9 ms 10240 KB Output is correct
10 Correct 7 ms 10112 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 10308 KB Output is correct
2 Correct 698 ms 10240 KB Output is correct
3 Correct 1199 ms 10224 KB Output is correct
4 Correct 876 ms 10140 KB Output is correct
5 Correct 702 ms 10140 KB Output is correct
6 Correct 476 ms 10324 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 10496 KB Output is correct
2 Correct 523 ms 10496 KB Output is correct
3 Correct 1033 ms 10112 KB Output is correct
4 Correct 814 ms 10144 KB Output is correct
5 Correct 751 ms 10168 KB Output is correct
6 Correct 423 ms 10240 KB Output is correct
7 Correct 477 ms 10496 KB Output is correct
8 Correct 7 ms 10112 KB Output is correct
9 Correct 11 ms 10112 KB Output is correct
10 Correct 8 ms 10144 KB Output is correct
11 Correct 586 ms 10144 KB Output is correct
12 Correct 462 ms 10484 KB Output is correct
13 Correct 533 ms 10492 KB Output is correct
14 Correct 560 ms 10240 KB Output is correct
15 Correct 73 ms 10140 KB Output is correct
16 Correct 94 ms 10332 KB Output is correct
17 Correct 148 ms 10308 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 981 ms 10140 KB Output is correct
2 Correct 677 ms 10280 KB Output is correct
3 Correct 653 ms 10292 KB Output is correct
4 Correct 8 ms 10404 KB Output is correct
5 Correct 15 ms 10264 KB Output is correct
6 Correct 8 ms 10144 KB Output is correct
7 Correct 636 ms 10144 KB Output is correct
8 Correct 982 ms 9984 KB Output is correct
9 Correct 650 ms 10136 KB Output is correct
10 Correct 586 ms 10144 KB Output is correct
11 Correct 12 ms 10148 KB Output is correct
12 Correct 11 ms 10112 KB Output is correct
13 Correct 9 ms 10112 KB Output is correct
14 Correct 10 ms 10140 KB Output is correct
15 Correct 7 ms 10144 KB Output is correct
16 Correct 541 ms 10140 KB Output is correct
17 Correct 597 ms 10136 KB Output is correct
18 Correct 585 ms 10144 KB Output is correct
19 Correct 516 ms 10140 KB Output is correct
20 Correct 544 ms 10140 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 10480 KB Output is correct
2 Correct 493 ms 10496 KB Output is correct
3 Correct 928 ms 10140 KB Output is correct
4 Correct 696 ms 10140 KB Output is correct
5 Correct 654 ms 10292 KB Output is correct
6 Correct 471 ms 10496 KB Output is correct
7 Correct 489 ms 10524 KB Output is correct
8 Correct 9 ms 10144 KB Output is correct
9 Correct 10 ms 10112 KB Output is correct
10 Correct 7 ms 10144 KB Output is correct
11 Correct 542 ms 10428 KB Output is correct
12 Correct 654 ms 10240 KB Output is correct
13 Correct 979 ms 10140 KB Output is correct
14 Correct 777 ms 10140 KB Output is correct
15 Correct 698 ms 10112 KB Output is correct
16 Correct 477 ms 10368 KB Output is correct
17 Correct 712 ms 10144 KB Output is correct
18 Correct 487 ms 10480 KB Output is correct
19 Correct 491 ms 10496 KB Output is correct
20 Correct 489 ms 10240 KB Output is correct
21 Correct 68 ms 10144 KB Output is correct
22 Correct 81 ms 10344 KB Output is correct
23 Correct 119 ms 10316 KB Output is correct
24 Correct 12 ms 10140 KB Output is correct
25 Correct 11 ms 10152 KB Output is correct
26 Correct 10 ms 10112 KB Output is correct
27 Correct 9 ms 10148 KB Output is correct
28 Correct 7 ms 10144 KB Output is correct
29 Correct 517 ms 10160 KB Output is correct
30 Correct 643 ms 10144 KB Output is correct
31 Correct 613 ms 10140 KB Output is correct
32 Correct 620 ms 10112 KB Output is correct
33 Correct 606 ms 10148 KB Output is correct
34 Correct 364 ms 10232 KB Output is correct
35 Correct 551 ms 10496 KB Output is correct
36 Correct 507 ms 10548 KB Output is correct
37 Correct 464 ms 10360 KB Output is correct
38 Correct 510 ms 10488 KB Output is correct
39 Correct 611 ms 10264 KB Output is correct
40 Correct 623 ms 10232 KB Output is correct
41 Correct 479 ms 10248 KB Output is correct
42 Correct 73 ms 10296 KB Output is correct
43 Correct 149 ms 10312 KB Output is correct
44 Correct 151 ms 10256 KB Output is correct
45 Correct 159 ms 10688 KB Output is correct
46 Correct 304 ms 10240 KB Output is correct
47 Correct 424 ms 10224 KB Output is correct
48 Correct 88 ms 10496 KB Output is correct
49 Correct 71 ms 10496 KB Output is correct