oj.uz

Submission #432725

# Submission time Handle Problem Language Result Execution time Memory
432725 2021-06-18T12:52:55 Z Hazem Stations (IOI20_stations) C++14
10 / 100
 1039 ms 604 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

const int N = 2e3;
int cnt = 0;

int dfs(int i,int pre,vector<int> &ret,vector<int> adj[]){

	int mx = cnt;
	ret[i] = cnt++;
	
	for(int j=0;j<adj[i].size();j++){
		int v = adj[i][j];
		if(v==pre)continue;

		mx = max(mx,dfs(v,i,ret,adj));
	}
	ret[i] |= mx<<10;
	return mx;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	
	vector<int>adj[N];
	for(int i=0;i<n-1;i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	vector<int> ret = vector<int>(n,0);
	dfs(0,0,ret,adj);
	return ret;
}

int get_val(int x,int l,int r){

	int ret = 0;
	for(int i=l;i<=r;i++)
		ret |= (1<<(i-l))*(((1<<i)&x)>0);
	return ret;
}

bool cmp(int x,int y){

	return get_val(x,0,9)<get_val(y,0,9);
}

int find_next_station(int s, int t, std::vector<int> c) {
	
	int s1 = get_val(s,0,9);	int t1 = get_val(t,0,9);	
	sort(c.begin(),c.end(),cmp);
	
	if(t1<s1)
		return c[0];
	
	vector<int>vec;
	for(int i=1;i<c.size();i++)
		vec.push_back(get_val(c[i],0,9));

	vec.push_back(get_val(c.back(),10,20)+1);
	for(int i=0;i<(int)vec.size()-1;i++)
		if(t1>=vec[i]&&t1<vec[i+1])
			return c[i+1];
	return c[0];
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1039 ms 472 KB Output is correct
2 Correct 734 ms 484 KB Output is correct
3 Correct 713 ms 492 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 6 ms 528 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 644 ms 484 KB Output is correct
8 Correct 953 ms 488 KB Output is correct
9 Correct 703 ms 528 KB Output is correct
10 Correct 647 ms 484 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 5 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 535 ms 492 KB Output is correct
17 Correct 519 ms 528 KB Output is correct
18 Correct 519 ms 412 KB Output is correct
19 Correct 478 ms 528 KB Output is correct
20 Correct 542 ms 556 KB Output is correct

Subtask #5
0 / 61.0

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