oj.uz

Submission #432732

# Submission time Handle Problem Language Result Execution time Memory
432732 2021-06-18T12:55:13 Z Hazem Stations (IOI20_stations) C++14
10 / 100
 971 ms 856 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,22)+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 3 ms 328 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 6 ms 284 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 4 ms 456 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 970 ms 400 KB Output is correct
2 Correct 653 ms 488 KB Output is correct
3 Correct 650 ms 528 KB Output is correct
4 Correct 3 ms 548 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 616 ms 528 KB Output is correct
8 Correct 971 ms 476 KB Output is correct
9 Correct 686 ms 592 KB Output is correct
10 Correct 643 ms 476 KB Output is correct
11 Correct 11 ms 596 KB Output is correct
12 Correct 5 ms 592 KB Output is correct
13 Correct 7 ms 596 KB Output is correct
14 Correct 6 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 510 ms 488 KB Output is correct
17 Correct 541 ms 528 KB Output is correct
18 Correct 485 ms 488 KB Output is correct
19 Correct 496 ms 528 KB Output is correct
20 Correct 507 ms 528 KB Output is correct

Subtask #5
0 / 61.0

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