oj.uz

Submission #404342

# Submission time Handle Problem Language Result Execution time Memory
404342 2021-05-14T08:31:09 Z AmineTrabelsi Stations (IOI20_stations) C++14
69.868 / 100
 1117 ms 744 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int Mx = 1010;
int timer = 0;
int tin[Mx],tout[Mx];
void dfs(int node,int par,vector<int> &labels,vector<vector<int>> &tr,bool parity){
    tin[node] = timer++;
    for(auto i:tr[node]){
        if(i != par){
            dfs(i,node,labels,tr,!parity);
        }
    }
    tout[node] = timer++;
    labels[node] = (parity ? tin[node] : tout[node]);
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    vector<int> labels(n);
    vector<vector<int>> tr(n+1,vector<int>(0));
	for (int i = 0; i < n-1; i++) {
		tr[u[i]].push_back(v[i]);
        tr[v[i]].push_back(u[i]);
	}
    dfs(0,-1,labels,tr,1);
    for(int i=0;i<n;i++){
        labels[i]/=2;
    }
	return labels;
}
int find_next_station(int s, int t, vector<int> c) {
    if ((int)c.size() == 1) return c.back();
    if (c.front() > s){
        // s in tin
        int l = s, r = c[(int)c.size() - 2];
        if (l > t || r < t) return c.back();
        int pos = lower_bound(c.begin(), c.end(), t) - c.begin();
        return c[pos];
    }
    // s is tout
    int l = c[1], r = s;
    if (l > t || r < t) return c.front();
    int pos = upper_bound(c.begin(), c.end(), t) - c.begin() - 1;
    return c[pos];
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 668 KB Output is correct
2 Correct 521 ms 616 KB Output is correct
3 Correct 1067 ms 480 KB Output is correct
4 Correct 808 ms 488 KB Output is correct
5 Correct 715 ms 400 KB Output is correct
6 Correct 477 ms 744 KB Output is correct
7 Correct 464 ms 612 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 629 ms 484 KB Output is correct
12 Correct 560 ms 712 KB Output is correct
13 Correct 613 ms 692 KB Output is correct
14 Correct 582 ms 480 KB Output is correct
15 Correct 65 ms 448 KB Output is correct
16 Correct 59 ms 528 KB Output is correct
17 Correct 108 ms 528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 476 KB Output is correct
2 Correct 769 ms 400 KB Output is correct
3 Correct 698 ms 604 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 692 ms 484 KB Output is correct
8 Correct 847 ms 476 KB Output is correct
9 Correct 874 ms 528 KB Output is correct
10 Correct 704 ms 532 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 8 ms 468 KB Output is correct
13 Correct 6 ms 476 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 476 KB Output is correct
16 Correct 562 ms 492 KB Output is correct
17 Correct 551 ms 484 KB Output is correct
18 Correct 631 ms 484 KB Output is correct
19 Correct 660 ms 528 KB Output is correct
20 Correct 666 ms 400 KB Output is correct

Subtask #5
43.868 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 570 ms 688 KB Partially correct
2 Partially correct 592 ms 644 KB Partially correct
3 Correct 1109 ms 484 KB Output is correct
4 Correct 833 ms 400 KB Output is correct
5 Correct 709 ms 400 KB Output is correct
6 Partially correct 501 ms 648 KB Partially correct
7 Correct 552 ms 484 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 5 ms 420 KB Output is correct
10 Correct 2 ms 476 KB Output is correct
11 Partially correct 603 ms 528 KB Partially correct
12 Partially correct 620 ms 544 KB Partially correct
13 Correct 1013 ms 400 KB Output is correct
14 Correct 697 ms 484 KB Output is correct
15 Correct 620 ms 528 KB Output is correct
16 Correct 530 ms 584 KB Output is correct
17 Correct 788 ms 400 KB Output is correct
18 Partially correct 443 ms 736 KB Partially correct
19 Partially correct 592 ms 712 KB Partially correct
20 Correct 523 ms 528 KB Output is correct
21 Correct 74 ms 400 KB Output is correct
22 Partially correct 87 ms 528 KB Partially correct
23 Partially correct 139 ms 604 KB Partially correct
24 Correct 7 ms 480 KB Output is correct
25 Correct 7 ms 468 KB Output is correct
26 Correct 6 ms 468 KB Output is correct
27 Correct 5 ms 468 KB Output is correct
28 Correct 3 ms 476 KB Output is correct
29 Correct 568 ms 400 KB Output is correct
30 Correct 563 ms 444 KB Output is correct
31 Correct 561 ms 400 KB Output is correct
32 Correct 648 ms 400 KB Output is correct
33 Correct 628 ms 400 KB Output is correct
34 Partially correct 366 ms 620 KB Partially correct
35 Partially correct 516 ms 700 KB Partially correct
36 Partially correct 477 ms 600 KB Partially correct
37 Partially correct 544 ms 680 KB Partially correct
38 Partially correct 591 ms 528 KB Partially correct
39 Partially correct 601 ms 732 KB Partially correct
40 Partially correct 485 ms 608 KB Partially correct
41 Partially correct 633 ms 608 KB Partially correct
42 Partially correct 73 ms 576 KB Partially correct
43 Partially correct 152 ms 528 KB Partially correct
44 Partially correct 125 ms 528 KB Partially correct
45 Partially correct 163 ms 488 KB Partially correct
46 Partially correct 365 ms 528 KB Partially correct
47 Partially correct 309 ms 616 KB Partially correct
48 Partially correct 90 ms 640 KB Partially correct
49 Partially correct 78 ms 624 KB Partially correct