oj.uz

Submission #826656

# Submission time Handle Problem Language Result Execution time Memory
826656 2023-08-15T19:07:38 Z Marco_Escandon Stations (IOI20_stations) C++17
100 / 100
 844 ms 876 KB 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll vis=0;
vector<int> sol;
vector<vector<ll>> cad;
void dfs(ll node,ll p, ll p2)
{
    if(p2%2==0)
    {
        sol[node]=vis;
        vis++;
    }

    for(auto i:cad[node])
    {
        if(i!=p)
        {
            dfs(i,node,p2+1);
        }
    }
    if(p2%2==1)
    {
        sol[node]=vis;
        vis++;
    }
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    vis=0;
    cad.assign(n+5,vector<ll>());
    for(int i=0; i<u.size(); i++)
    {
        cad[u[i]].push_back(v[i]);
        cad[v[i]].push_back(u[i]);
    }
    sol.clear();;
    sol.assign(n,0);
    dfs(0,-1,2);
	return sol;
}

int find_next_station(int s, int t, std::vector<int> c) {
	sort(c.begin(), c.end());
	if(c.size()==1)return c[0];
	ll pl=0;
	for(auto i:c)
    {
        if(i>s)
            pl++;
    }
    if(pl==0)
    {

        if(c[0]>=t||s<t)
            return c[0];
        for(int i=c.size()-1; i>-1; i--)
        {
            if(c[i]<=t)
                return c[i];
        }
    }
    else
    {
        if(c.back()<=t||t<s)
            return c.back();
        for(int i=0; i<c.size(); i++)
        {
            if(c[i]>=t)
                return c[i];
        }
    }
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0; i<u.size(); i++)
      |                  ~^~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i=0; i<c.size(); i++)
      |                      ~^~~~~~~~~
stations.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
   73 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 688 KB Output is correct
2 Correct 298 ms 692 KB Output is correct
3 Correct 729 ms 416 KB Output is correct
4 Correct 543 ms 500 KB Output is correct
5 Correct 569 ms 416 KB Output is correct
6 Correct 341 ms 636 KB Output is correct
7 Correct 360 ms 544 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 0 ms 504 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 636 KB Output is correct
2 Correct 424 ms 576 KB Output is correct
3 Correct 686 ms 416 KB Output is correct
4 Correct 644 ms 548 KB Output is correct
5 Correct 505 ms 420 KB Output is correct
6 Correct 333 ms 612 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 636 KB Output is correct
2 Correct 343 ms 676 KB Output is correct
3 Correct 732 ms 416 KB Output is correct
4 Correct 482 ms 500 KB Output is correct
5 Correct 383 ms 420 KB Output is correct
6 Correct 316 ms 544 KB Output is correct
7 Correct 336 ms 544 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 574 ms 504 KB Output is correct
12 Correct 472 ms 544 KB Output is correct
13 Correct 312 ms 628 KB Output is correct
14 Correct 290 ms 544 KB Output is correct
15 Correct 33 ms 512 KB Output is correct
16 Correct 45 ms 612 KB Output is correct
17 Correct 76 ms 600 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 416 KB Output is correct
2 Correct 476 ms 416 KB Output is correct
3 Correct 452 ms 416 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 1 ms 488 KB Output is correct
7 Correct 463 ms 504 KB Output is correct
8 Correct 612 ms 500 KB Output is correct
9 Correct 484 ms 544 KB Output is correct
10 Correct 527 ms 416 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 2 ms 500 KB Output is correct
13 Correct 4 ms 500 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 389 ms 504 KB Output is correct
17 Correct 406 ms 420 KB Output is correct
18 Correct 369 ms 420 KB Output is correct
19 Correct 345 ms 504 KB Output is correct
20 Correct 376 ms 512 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 632 KB Output is correct
2 Correct 415 ms 544 KB Output is correct
3 Correct 712 ms 504 KB Output is correct
4 Correct 582 ms 508 KB Output is correct
5 Correct 430 ms 420 KB Output is correct
6 Correct 424 ms 544 KB Output is correct
7 Correct 364 ms 548 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 309 ms 632 KB Output is correct
12 Correct 406 ms 508 KB Output is correct
13 Correct 739 ms 504 KB Output is correct
14 Correct 547 ms 504 KB Output is correct
15 Correct 431 ms 504 KB Output is correct
16 Correct 364 ms 544 KB Output is correct
17 Correct 428 ms 416 KB Output is correct
18 Correct 307 ms 712 KB Output is correct
19 Correct 422 ms 736 KB Output is correct
20 Correct 343 ms 504 KB Output is correct
21 Correct 41 ms 468 KB Output is correct
22 Correct 46 ms 672 KB Output is correct
23 Correct 105 ms 600 KB Output is correct
24 Correct 5 ms 492 KB Output is correct
25 Correct 3 ms 500 KB Output is correct
26 Correct 3 ms 500 KB Output is correct
27 Correct 2 ms 488 KB Output is correct
28 Correct 1 ms 500 KB Output is correct
29 Correct 384 ms 420 KB Output is correct
30 Correct 336 ms 420 KB Output is correct
31 Correct 459 ms 420 KB Output is correct
32 Correct 421 ms 500 KB Output is correct
33 Correct 364 ms 416 KB Output is correct
34 Correct 229 ms 672 KB Output is correct
35 Correct 371 ms 716 KB Output is correct
36 Correct 347 ms 708 KB Output is correct
37 Correct 379 ms 760 KB Output is correct
38 Correct 317 ms 708 KB Output is correct
39 Correct 340 ms 728 KB Output is correct
40 Correct 355 ms 708 KB Output is correct
41 Correct 413 ms 628 KB Output is correct
42 Correct 46 ms 620 KB Output is correct
43 Correct 77 ms 532 KB Output is correct
44 Correct 128 ms 568 KB Output is correct
45 Correct 116 ms 624 KB Output is correct
46 Correct 294 ms 504 KB Output is correct
47 Correct 292 ms 636 KB Output is correct
48 Correct 43 ms 824 KB Output is correct
49 Correct 47 ms 876 KB Output is correct