oj.uz

Submission #1095751

# Submission time Handle Problem Language Result Execution time Memory
1095751 2024-10-03T06:36:46 Z Newtonabc Stations (IOI20_stations) C++14
21 / 100
 648 ms 1036 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int tmpcase1,cnt=0,root=-1;
bool case1;
vector<int> adj[N],lb;

void labelcase1(int u,int p){
	lb[u]=cnt++;
	for(int i=0;i<adj[u].size();i++){
		if(adj[u][i]!=p) labelcase1(adj[u][i],u);
	}
}
void labelcase3(int u,int p){
	lb[u]=cnt;
	bool next=false;
	for(int i=0;i<adj[u].size();i++){
		if(adj[u][i]!=p){
			next=true;
			cnt++;
			labelcase3(adj[u][i],u);
		}
	}
	if(!next) cnt+=999;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	lb.resize(n);
	cnt=0,case1=true;
	for(int i=0;i<n-1;i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	
	for(int i=0;i<n;i++){
		if(adj[i].size()==1) tmpcase1=i;
		if(adj[i].size()>2) case1=false,root=i;
	}
	if(case1) labelcase1(tmpcase1,-1);
	else labelcase3(root,-1);
	/*case2
	for(int i=0;i<n;i++) lb[i]=i;*/
	for(int i=0;i<n;i++) adj[i].clear();
	/*for(int i=0;i<lb.size();i++) cout<<lb[i] <<" ";
	cout<<"\n\n\n";*/
	return lb;
}

int find_next_station(int s, int t, vector<int> c) {
	/*case1
	if(c.size()==1) return c[0];
	if(s<t) return max(c[0],c[1]);
	return min(c[0],c[1]);*/
	/*case2
	int cnts=0,cntt=0,tmps=s+1,tmpt=t+1;
	s++,t++;
	while(tmps!=0) cnts++,tmps/=2;
	while(tmpt!=0) cntt++,tmpt/=2;
	if(cnts>cntt) return (s/2)-1;
	if(cntt>cnts){
		while(true){
			if(t==s*2) return s*2-1;
			if(t==s*2+1) return s*2;
			if(t==s || t<s) return s/2-1;
			t/=2;
		}
	}
	return s/2-1;*/
	int ind;
	if(c.size()==1) return c[0];
	if(c.size()>2){
		ind=upper_bound(c.begin(),c.end(),t)-c.begin()-1;
		return c[ind];
	}
	if(abs(t-s)>=1000 || t<s) return c[0];
	return c[1];
	
	
}

Compilation message

stations.cpp: In function 'void labelcase1(int, int)':
stations.cpp:11:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~
stations.cpp: In function 'void labelcase3(int, int)':
stations.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 684 KB Output is correct
2 Correct 302 ms 692 KB Output is correct
3 Correct 615 ms 684 KB Output is correct
4 Correct 425 ms 684 KB Output is correct
5 Correct 421 ms 684 KB Output is correct
6 Correct 329 ms 684 KB Output is correct
7 Correct 343 ms 684 KB Output is correct
8 Correct 2 ms 764 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 0 ms 768 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 684 KB Output is correct
2 Correct 320 ms 688 KB Output is correct
3 Correct 590 ms 684 KB Output is correct
4 Correct 418 ms 684 KB Output is correct
5 Correct 406 ms 684 KB Output is correct
6 Correct 352 ms 688 KB Output is correct
7 Correct 287 ms 684 KB Output is correct
8 Correct 2 ms 928 KB Output is correct
9 Correct 1 ms 780 KB Output is correct
10 Correct 0 ms 764 KB Output is correct
11 Correct 416 ms 684 KB Output is correct
12 Correct 317 ms 788 KB Output is correct
13 Correct 321 ms 1036 KB Output is correct
14 Correct 286 ms 684 KB Output is correct
15 Correct 30 ms 772 KB Output is correct
16 Correct 36 ms 716 KB Output is correct
17 Correct 64 ms 684 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 684 KB Output is correct
2 Correct 435 ms 684 KB Output is correct
3 Correct 401 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 1 ms 764 KB Output is correct
7 Correct 422 ms 684 KB Output is correct
8 Correct 560 ms 684 KB Output is correct
9 Correct 459 ms 684 KB Output is correct
10 Correct 389 ms 684 KB Output is correct
11 Incorrect 3 ms 768 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 684 KB Output is correct
2 Correct 299 ms 684 KB Output is correct
3 Correct 648 ms 684 KB Output is correct
4 Correct 457 ms 684 KB Output is correct
5 Correct 443 ms 944 KB Output is correct
6 Correct 292 ms 684 KB Output is correct
7 Correct 335 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Incorrect 323 ms 684 KB Wrong query response.
12 Halted 0 ms 0 KB -