oj.uz

Submission #565167

# Submission time Handle Problem Language Result Execution time Memory
565167 2022-05-20T11:15:27 Z Ronin13 Stations (IOI20_stations) C++14
100 / 100
 855 ms 828 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;


const int inf = 1e9 + 1;
const ll linf = 1e18 + 1;
const int NMAX = 1001;

vector <vector <int> > g (NMAX);
vector <int> col(NMAX);
int timer = 0;
vector <int> t_in(NMAX);
vector <int> t_out(NMAX);
void dfs(int v,  int e = -1){
    t_in[v] = timer++;
    for(int to : g[v]){
        if(to == e) continue;
        col[to] = 1 ^ col[v];
        dfs(to, v);
    }
    t_out[v] = timer++;
}



std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    for(int v = 0; v < n; v++){
        t_in[v] = t_out[v] = col[v] = 0;
        g[v].clear();
        timer = 0;
    }
	std::vector<int> labels(n);
	for(int i = 0; i < n - 1; i++){
        int uu = u[i], vv = v[i];
        g[uu].pb(vv);
        g[vv].pb(uu);
	}
	dfs(0);
	vector <pii> vec;
    for(int i = 0; i < n; i++){
        if(col[i] == 0) vec.pb({t_in[i], i});
        else vec.pb({t_out[i], i});
    }
    sort(vec.begin(), vec.end());
    int ind = 0;
    for(auto to : vec){
        int x = to.f, y = to.s;
        labels[y] = ind++;
    }
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	bool bl = false;
    if(c[0] > s) bl = true;
    if(bl){
        sort(c.begin(), c.end());
        if(t >= c.back()) return c.back();
        //if(c[0] >= t ) return c.back();
        if(t < s) return c.back();
        for(int i = c.size() - 1 ; i >= 0; i--){
            if(c[i] < t) return c[i + 1];
        }
        return c[0];
    }
    else{
        sort(c.begin(), c.end());
        /*for(int to : c){
            cout << to << " ";
        }*/
        if(t > s) return c[0];
        if(t <= c[0]) return c[0];
        //if(c.back() <= t) return c[0];
        for(int i = 0; i < c.size(); i++){
            if(c[i] > t) return c[i - 1];
        }
        return c.back();
    }
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:57:13: warning: unused variable 'x' [-Wunused-variable]
   57 |         int x = to.f, y = to.s;
      |             ^
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:84:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int i = 0; i < c.size(); i++){
      |                        ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 536 KB Output is correct
2 Correct 436 ms 672 KB Output is correct
3 Correct 833 ms 672 KB Output is correct
4 Correct 607 ms 544 KB Output is correct
5 Correct 507 ms 548 KB Output is correct
6 Correct 398 ms 676 KB Output is correct
7 Correct 411 ms 676 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 1 ms 628 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 804 KB Output is correct
2 Correct 417 ms 544 KB Output is correct
3 Correct 779 ms 528 KB Output is correct
4 Correct 562 ms 416 KB Output is correct
5 Correct 512 ms 548 KB Output is correct
6 Correct 372 ms 544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 532 KB Output is correct
2 Correct 410 ms 672 KB Output is correct
3 Correct 776 ms 416 KB Output is correct
4 Correct 608 ms 644 KB Output is correct
5 Correct 548 ms 548 KB Output is correct
6 Correct 423 ms 676 KB Output is correct
7 Correct 381 ms 548 KB Output is correct
8 Correct 2 ms 756 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 488 ms 676 KB Output is correct
12 Correct 457 ms 800 KB Output is correct
13 Correct 467 ms 648 KB Output is correct
14 Correct 401 ms 724 KB Output is correct
15 Correct 49 ms 748 KB Output is correct
16 Correct 54 ms 728 KB Output is correct
17 Correct 91 ms 672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 770 ms 420 KB Output is correct
2 Correct 551 ms 668 KB Output is correct
3 Correct 530 ms 544 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 4 ms 620 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 564 ms 672 KB Output is correct
8 Correct 855 ms 548 KB Output is correct
9 Correct 563 ms 676 KB Output is correct
10 Correct 534 ms 544 KB Output is correct
11 Correct 5 ms 704 KB Output is correct
12 Correct 5 ms 748 KB Output is correct
13 Correct 4 ms 620 KB Output is correct
14 Correct 4 ms 500 KB Output is correct
15 Correct 2 ms 628 KB Output is correct
16 Correct 457 ms 416 KB Output is correct
17 Correct 430 ms 544 KB Output is correct
18 Correct 416 ms 668 KB Output is correct
19 Correct 452 ms 420 KB Output is correct
20 Correct 454 ms 548 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 804 KB Output is correct
2 Correct 362 ms 660 KB Output is correct
3 Correct 754 ms 416 KB Output is correct
4 Correct 575 ms 548 KB Output is correct
5 Correct 480 ms 536 KB Output is correct
6 Correct 395 ms 660 KB Output is correct
7 Correct 413 ms 664 KB Output is correct
8 Correct 2 ms 756 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 0 ms 760 KB Output is correct
11 Correct 424 ms 664 KB Output is correct
12 Correct 436 ms 716 KB Output is correct
13 Correct 666 ms 668 KB Output is correct
14 Correct 559 ms 544 KB Output is correct
15 Correct 468 ms 672 KB Output is correct
16 Correct 435 ms 676 KB Output is correct
17 Correct 563 ms 548 KB Output is correct
18 Correct 404 ms 672 KB Output is correct
19 Correct 417 ms 664 KB Output is correct
20 Correct 411 ms 672 KB Output is correct
21 Correct 51 ms 748 KB Output is correct
22 Correct 69 ms 672 KB Output is correct
23 Correct 96 ms 672 KB Output is correct
24 Correct 6 ms 488 KB Output is correct
25 Correct 7 ms 748 KB Output is correct
26 Correct 4 ms 620 KB Output is correct
27 Correct 3 ms 748 KB Output is correct
28 Correct 1 ms 628 KB Output is correct
29 Correct 458 ms 536 KB Output is correct
30 Correct 461 ms 548 KB Output is correct
31 Correct 431 ms 676 KB Output is correct
32 Correct 442 ms 420 KB Output is correct
33 Correct 424 ms 544 KB Output is correct
34 Correct 248 ms 684 KB Output is correct
35 Correct 375 ms 788 KB Output is correct
36 Correct 412 ms 668 KB Output is correct
37 Correct 405 ms 660 KB Output is correct
38 Correct 420 ms 676 KB Output is correct
39 Correct 394 ms 788 KB Output is correct
40 Correct 426 ms 724 KB Output is correct
41 Correct 369 ms 676 KB Output is correct
42 Correct 56 ms 676 KB Output is correct
43 Correct 74 ms 672 KB Output is correct
44 Correct 115 ms 544 KB Output is correct
45 Correct 146 ms 628 KB Output is correct
46 Correct 293 ms 536 KB Output is correct
47 Correct 276 ms 676 KB Output is correct
48 Correct 54 ms 700 KB Output is correct
49 Correct 55 ms 828 KB Output is correct