oj.uz

Submission #1095764

# Submission time Handle Problem Language Result Execution time Memory
1095764 2024-10-03T06:48:34 Z Newtonabc Stations (IOI20_stations) C++14
21 / 100
 661 ms 1040 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 387 ms 684 KB Output is correct
2 Correct 323 ms 684 KB Output is correct
3 Correct 655 ms 684 KB Output is correct
4 Correct 462 ms 940 KB Output is correct
5 Correct 405 ms 684 KB Output is correct
6 Correct 306 ms 684 KB Output is correct
7 Correct 296 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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 520 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 360 ms 684 KB Output is correct
2 Correct 306 ms 684 KB Output is correct
3 Correct 604 ms 684 KB Output is correct
4 Correct 434 ms 684 KB Output is correct
5 Correct 436 ms 684 KB Output is correct
6 Correct 332 ms 684 KB Output is correct
7 Correct 299 ms 684 KB Output is correct
8 Correct 1 ms 780 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 420 ms 684 KB Output is correct
12 Correct 333 ms 1040 KB Output is correct
13 Correct 339 ms 928 KB Output is correct
14 Correct 290 ms 684 KB Output is correct
15 Correct 34 ms 772 KB Output is correct
16 Correct 34 ms 768 KB Output is correct
17 Correct 63 ms 768 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 688 KB Output is correct
2 Correct 445 ms 684 KB Output is correct
3 Correct 411 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 370 ms 684 KB Output is correct
8 Correct 661 ms 684 KB Output is correct
9 Correct 454 ms 684 KB Output is correct
10 Correct 354 ms 684 KB Output is correct
11 Incorrect 2 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 370 ms 684 KB Output is correct
2 Correct 318 ms 684 KB Output is correct
3 Correct 630 ms 684 KB Output is correct
4 Correct 453 ms 688 KB Output is correct
5 Correct 399 ms 684 KB Output is correct
6 Correct 300 ms 684 KB Output is correct
7 Correct 308 ms 684 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 0 ms 776 KB Output is correct
11 Incorrect 335 ms 684 KB Wrong query response.
12 Halted 0 ms 0 KB -