oj.uz

Submission #307641

# Submission time Handle Problem Language Result Execution time Memory
307641 2020-09-28T22:09:09 Z giorgikob Stations (IOI20_stations) C++14
76 / 100
 994 ms 1304 KB 
#include "stations.h"
#include <vector>
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e3+5;

vector<int>gr[N];

int cnt = 0;
int fix[N];
int mn[N];
int in[N], out[N];

void dfs(int x, int h, vector<int>&v){
    fix[x] = 1;
    in[x] = cnt;cnt++;
    for(auto to : gr[x]){
        if(fix[to]) continue;
        dfs(to,h+1,v);
    }
    out[x] = cnt;cnt++;
    if(h%2){
        v[x] = out[x];
    } else {
        v[x] = in[x];
    }
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {

	std::vector<int> labels(n,0);
	for(int i = 0; i < u.size(); i++){
        int x = u[i];
        int y = v[i];
        gr[x].pb(y);
        gr[y].pb(x);
	}

	cnt = 0;
    dfs(0,0,labels);

	for(int i = 0; i < n; i++) gr[i].clear(), fix[i] = 0;

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    /*cout << "test case" << endl;
    cout << s << " " << t << endl;
    for(auto x : c) cout << x << " "; cout << endl;
    cout << "end of test case" << endl;
    */
    if(c.size() == 1) return c[0];

    if(c[0] < s){
        for(int i = 1; i < c.size(); i++){
            int in = c[i];
            int out = (c[i] == c.back()) ? (s-1) : (c[i+1] - 1);
            if(in <= t && t <= out) return c[i];
        }
        return c[0];
    } else {
        for(int i = 0; i < c.size() - 1; i++){
            int in = (i == 0) ? (s + 1) : (c[i-1] + 1);
            int out = c[i];
            if(in <= t && t <= out) return c[i];
        }
        return c.back();
    }
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 1024 KB Output is correct
2 Correct 462 ms 1024 KB Output is correct
3 Correct 890 ms 1032 KB Output is correct
4 Correct 821 ms 868 KB Output is correct
5 Correct 769 ms 872 KB Output is correct
6 Correct 499 ms 1016 KB Output is correct
7 Correct 499 ms 768 KB Output is correct
8 Correct 2 ms 864 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 679 ms 880 KB Output is correct
12 Correct 457 ms 1016 KB Output is correct
13 Correct 468 ms 1008 KB Output is correct
14 Correct 431 ms 768 KB Output is correct
15 Correct 54 ms 768 KB Output is correct
16 Correct 68 ms 956 KB Output is correct
17 Correct 120 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 768 KB Output is correct
2 Correct 823 ms 768 KB Output is correct
3 Correct 768 ms 768 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 2 ms 864 KB Output is correct
7 Correct 657 ms 768 KB Output is correct
8 Correct 867 ms 1040 KB Output is correct
9 Correct 684 ms 864 KB Output is correct
10 Correct 589 ms 872 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 6 ms 876 KB Output is correct
13 Correct 4 ms 768 KB Output is correct
14 Correct 4 ms 884 KB Output is correct
15 Correct 1 ms 876 KB Output is correct
16 Correct 511 ms 768 KB Output is correct
17 Correct 579 ms 768 KB Output is correct
18 Correct 519 ms 876 KB Output is correct
19 Correct 581 ms 768 KB Output is correct
20 Correct 602 ms 880 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 544 ms 1024 KB Partially correct
2 Partially correct 465 ms 1024 KB Partially correct
3 Correct 859 ms 768 KB Output is correct
4 Correct 730 ms 1024 KB Output is correct
5 Correct 734 ms 768 KB Output is correct
6 Partially correct 459 ms 1304 KB Partially correct
7 Partially correct 445 ms 780 KB Partially correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Partially correct 468 ms 896 KB Partially correct
12 Partially correct 534 ms 812 KB Partially correct
13 Correct 994 ms 868 KB Output is correct
14 Correct 778 ms 1032 KB Output is correct
15 Correct 742 ms 872 KB Output is correct
16 Partially correct 537 ms 768 KB Partially correct
17 Correct 646 ms 768 KB Output is correct
18 Partially correct 490 ms 1016 KB Partially correct
19 Partially correct 569 ms 1024 KB Partially correct
20 Partially correct 449 ms 784 KB Partially correct
21 Correct 59 ms 768 KB Output is correct
22 Partially correct 73 ms 828 KB Partially correct
23 Partially correct 115 ms 792 KB Partially correct
24 Correct 6 ms 896 KB Output is correct
25 Correct 6 ms 768 KB Output is correct
26 Correct 6 ms 768 KB Output is correct
27 Correct 4 ms 876 KB Output is correct
28 Correct 2 ms 896 KB Output is correct
29 Correct 551 ms 768 KB Output is correct
30 Correct 597 ms 864 KB Output is correct
31 Correct 566 ms 868 KB Output is correct
32 Correct 477 ms 868 KB Output is correct
33 Correct 579 ms 1040 KB Output is correct
34 Partially correct 426 ms 984 KB Partially correct
35 Partially correct 582 ms 1008 KB Partially correct
36 Partially correct 467 ms 1224 KB Partially correct
37 Partially correct 568 ms 1000 KB Partially correct
38 Partially correct 449 ms 1224 KB Partially correct
39 Partially correct 455 ms 1016 KB Partially correct
40 Partially correct 448 ms 1008 KB Partially correct
41 Partially correct 495 ms 1092 KB Partially correct
42 Partially correct 70 ms 768 KB Partially correct
43 Partially correct 103 ms 796 KB Partially correct
44 Partially correct 139 ms 768 KB Partially correct
45 Partially correct 173 ms 976 KB Partially correct
46 Partially correct 371 ms 816 KB Partially correct
47 Partially correct 338 ms 768 KB Partially correct
48 Partially correct 61 ms 1024 KB Partially correct
49 Partially correct 60 ms 992 KB Partially correct