oj.uz

Submission #308596

# Submission time Handle Problem Language Result Execution time Memory
308596 2020-10-01T14:55:34 Z nadorb Stations (IOI20_stations) C++14
10 / 100
 1033 ms 1008 KB 
#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){
    visit[v]=1;
    beki[v].first=ido;
    ido++;
    for(int i:graf[v]){
        if(!visit[i]){
            dfs(i,ido);
        }
    }
    beki[v].second=ido;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	graf.clear();
	visit.clear();
	beki.clear();
	graf.resize(n);
	visit.resize(n,0);
	beki.resize(n);
	int ido=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);
	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 3 ms 384 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=6010
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 545 ms 1008 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 878 ms 644 KB Output is correct
2 Correct 801 ms 640 KB Output is correct
3 Correct 653 ms 640 KB Output is correct
4 Correct 3 ms 752 KB Output is correct
5 Correct 8 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 582 ms 768 KB Output is correct
8 Correct 1033 ms 648 KB Output is correct
9 Correct 774 ms 644 KB Output is correct
10 Correct 660 ms 908 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 7 ms 656 KB Output is correct
13 Correct 6 ms 640 KB Output is correct
14 Correct 4 ms 656 KB Output is correct
15 Correct 2 ms 652 KB Output is correct
16 Correct 620 ms 800 KB Output is correct
17 Correct 564 ms 644 KB Output is correct
18 Correct 511 ms 640 KB Output is correct
19 Correct 507 ms 640 KB Output is correct
20 Correct 597 ms 640 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 571 ms 768 KB Wrong query response.
2 Halted 0 ms 0 KB -