Submission #308632

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
308632	2020-10-01T15:22:13 Z	nadorb	Stations (IOI20_stations)	C++14	52.3206 / 100	1103 ms	1116 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>>graf;
vector<int>visit;
vector<pair<int,int>>beki;

void dfs(int v,int &ido, int &tim){
    visit[v]=1;
    beki[v].first=ido;
    ido++;
    for(int i:graf[v]){
        if(!visit[i]){
            dfs(i,ido,tim);
        }
    }
    beki[v].second=tim;
    tim++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	graf.clear();   //clear+resize=assign
	visit.clear();
	beki.clear();
	graf.resize(n);
	visit.resize(n,0);
	beki.resize(n);
	int ido=0,tim=0;
	for (int i = 0; i < n-1; i++) {
		graf[u[i]].push_back(v[i]);
		graf[v[i]].push_back(u[i]);
	}
	dfs(0,ido,tim);
	for(int i=0;i<n;i++){
        labels[i]=beki[i].first*1000+beki[i].second;
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    pair<long long, long long>kezdo;
    pair<long long, long long>cel;
    kezdo.first=s/1000;
    kezdo.second=s%1000;
    cel.first=t/1000;
    cel.second=t%1000;
    int ki=c[0];
    if(kezdo.first<cel.first && kezdo.second>cel.second){  //else jo a c[0]
        for(unsigned long long i=1;i<c.size();i++){
            int cf=c[i]/1000,cs=c[i]%1000;
            if(cf<=cel.first && cs>=cel.second){
                ki=c[i];
                break;
            }
        }
    }

	return ki;
}

Subtask #1

0 / 5.0

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

Subtask #2

0 / 8.0

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

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	702 ms	1008 KB	Output is correct
2	Correct	481 ms	1008 KB	Output is correct
3	Correct	1057 ms	764 KB	Output is correct
4	Correct	821 ms	640 KB	Output is correct
5	Correct	605 ms	640 KB	Output is correct
6	Correct	584 ms	768 KB	Output is correct
7	Correct	546 ms	784 KB	Output is correct
8	Correct	3 ms	800 KB	Output is correct
9	Correct	3 ms	644 KB	Output is correct
10	Correct	1 ms	644 KB	Output is correct
11	Correct	714 ms	652 KB	Output is correct
12	Correct	540 ms	1000 KB	Output is correct
13	Correct	509 ms	1024 KB	Output is correct
14	Correct	551 ms	896 KB	Output is correct
15	Correct	66 ms	768 KB	Output is correct
16	Correct	73 ms	844 KB	Output is correct
17	Correct	160 ms	800 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	987 ms	644 KB	Output is correct
2	Correct	762 ms	640 KB	Output is correct
3	Correct	636 ms	640 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	5 ms	776 KB	Output is correct
6	Correct	2 ms	640 KB	Output is correct
7	Correct	649 ms	864 KB	Output is correct
8	Correct	1103 ms	640 KB	Output is correct
9	Correct	842 ms	1008 KB	Output is correct
10	Correct	706 ms	640 KB	Output is correct
11	Correct	7 ms	644 KB	Output is correct
12	Correct	5 ms	640 KB	Output is correct
13	Correct	6 ms	640 KB	Output is correct
14	Correct	5 ms	648 KB	Output is correct
15	Correct	1 ms	644 KB	Output is correct
16	Correct	615 ms	640 KB	Output is correct
17	Correct	553 ms	640 KB	Output is correct
18	Correct	599 ms	644 KB	Output is correct
19	Correct	555 ms	876 KB	Output is correct
20	Correct	562 ms	748 KB	Output is correct

Subtask #5

26.3206 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	654 ms	1008 KB	Partially correct
2	Partially correct	493 ms	768 KB	Partially correct
3	Correct	1059 ms	800 KB	Output is correct
4	Partially correct	873 ms	688 KB	Partially correct
5	Partially correct	646 ms	776 KB	Partially correct
6	Partially correct	487 ms	1016 KB	Partially correct
7	Partially correct	470 ms	768 KB	Partially correct
8	Partially correct	3 ms	772 KB	Partially correct
9	Partially correct	5 ms	776 KB	Partially correct
10	Partially correct	2 ms	640 KB	Partially correct
11	Partially correct	552 ms	768 KB	Partially correct
12	Partially correct	673 ms	768 KB	Partially correct
13	Correct	1067 ms	644 KB	Output is correct
14	Partially correct	654 ms	784 KB	Partially correct
15	Partially correct	661 ms	648 KB	Partially correct
16	Partially correct	454 ms	816 KB	Partially correct
17	Partially correct	653 ms	640 KB	Partially correct
18	Partially correct	476 ms	1000 KB	Partially correct
19	Partially correct	477 ms	1024 KB	Partially correct
20	Partially correct	459 ms	816 KB	Partially correct
21	Partially correct	73 ms	640 KB	Partially correct
22	Partially correct	78 ms	1116 KB	Partially correct
23	Partially correct	116 ms	804 KB	Partially correct
24	Partially correct	6 ms	656 KB	Partially correct
25	Partially correct	5 ms	640 KB	Partially correct
26	Partially correct	3 ms	640 KB	Partially correct
27	Partially correct	2 ms	640 KB	Partially correct
28	Partially correct	1 ms	640 KB	Partially correct
29	Partially correct	490 ms	640 KB	Partially correct
30	Partially correct	504 ms	640 KB	Partially correct
31	Partially correct	512 ms	652 KB	Partially correct
32	Partially correct	521 ms	640 KB	Partially correct
33	Partially correct	531 ms	644 KB	Partially correct
34	Partially correct	339 ms	1012 KB	Partially correct
35	Partially correct	451 ms	1008 KB	Partially correct
36	Partially correct	489 ms	1024 KB	Partially correct
37	Partially correct	494 ms	768 KB	Partially correct
38	Partially correct	535 ms	760 KB	Partially correct
39	Partially correct	514 ms	908 KB	Partially correct
40	Partially correct	514 ms	768 KB	Partially correct
41	Partially correct	555 ms	912 KB	Partially correct
42	Partially correct	70 ms	820 KB	Partially correct
43	Partially correct	144 ms	800 KB	Partially correct
44	Partially correct	147 ms	784 KB	Partially correct
45	Partially correct	225 ms	1024 KB	Partially correct
46	Partially correct	368 ms	788 KB	Partially correct
47	Partially correct	360 ms	788 KB	Partially correct
48	Partially correct	69 ms	756 KB	Partially correct
49	Partially correct	63 ms	768 KB	Partially correct