oj.uz

Submission #308590

# Submission time Handle Problem Language Result Execution time Memory
308590 2020-10-01T14:52:38 Z nadorb Stations (IOI20_stations) C++14
10 / 100
 1091 ms 1088 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<int,int>kezdo;
    pair<int,int>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(int 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;
}

Compilation message

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

Subtask #1
0 / 5.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=6010
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=1512
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1045 ms 640 KB Output is correct
2 Correct 831 ms 640 KB Output is correct
3 Correct 689 ms 768 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 5 ms 652 KB Output is correct
6 Correct 1 ms 648 KB Output is correct
7 Correct 731 ms 768 KB Output is correct
8 Correct 1091 ms 640 KB Output is correct
9 Correct 792 ms 640 KB Output is correct
10 Correct 720 ms 640 KB Output is correct
11 Correct 7 ms 652 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 9 ms 648 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 702 ms 768 KB Output is correct
17 Correct 659 ms 824 KB Output is correct
18 Correct 526 ms 640 KB Output is correct
19 Correct 589 ms 768 KB Output is correct
20 Correct 622 ms 640 KB Output is correct

Subtask #5
0 / 61.0

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