oj.uz

Submission #432751

# Submission time Handle Problem Language Result Execution time Memory
432751 2021-06-18T13:06:53 Z Hazem Stations (IOI20_stations) C++14
10 / 100
 891 ms 656 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,19)+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 412 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 5 ms 292 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 412 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 866 ms 468 KB Output is correct
2 Correct 674 ms 552 KB Output is correct
3 Correct 669 ms 528 KB Output is correct
4 Correct 4 ms 608 KB Output is correct
5 Correct 6 ms 608 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 647 ms 656 KB Output is correct
8 Correct 891 ms 400 KB Output is correct
9 Correct 680 ms 484 KB Output is correct
10 Correct 612 ms 480 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 6 ms 596 KB Output is correct
13 Correct 6 ms 592 KB Output is correct
14 Correct 7 ms 592 KB Output is correct
15 Correct 5 ms 596 KB Output is correct
16 Correct 528 ms 488 KB Output is correct
17 Correct 503 ms 528 KB Output is correct
18 Correct 517 ms 540 KB Output is correct
19 Correct 516 ms 600 KB Output is correct
20 Correct 550 ms 528 KB Output is correct

Subtask #5
0 / 61.0

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