oj.uz

Submission #743069

# Submission time Handle Problem Language Result Execution time Memory
743069 2023-05-17T07:44:45 Z salmon Drawing (CEOI22_drawing) C++14
10 / 100
 335 ms 30144 KB 
#include <bits/stdc++.h>
using namespace std;
int N;
int a,b;
vector<int> adjlst[200100];
map<pair<int,int>,int> mep;
int ans[200100];
vector<pair<int,int>> v;
deque<pair<int,int>> vtemp,vtap;
vector<pair<int,int>> convex;
int gloeb;

pair<int,int> m(pair<int,int> p, pair<int,int> p1){
	if(p.first - p1.first < 0){
		return make_pair(0 - (p.second - p1.second), abs(p.first - p1.first));
	}
	return make_pair(p.second - p1.second, p.first - p1.first);
}

bool compare(pair<int,int> m, pair<int,int> m1){
	if(m.first * (long long int) m1.second < m.second * (long long int) m1.first){
		return true;
	}
	return false;
}

void dfs(int i, int p){
	ans[mep[convex[gloeb]]] = i;
	gloeb++;
	
	for(int j : adjlst[i]){
		if(j != p){
			dfs(j,i);
		}
	}
}

int main(){
	scanf(" %d",&N);
	
	for(int i = 0; i < N - 1; i++){
		scanf(" %d",&a);
		scanf(" %d",&b);
		
		adjlst[a].push_back(b);
		adjlst[b].push_back(a);
	}
	
	for(int i = 0; i < N; i++){
		scanf(" %d",&a);
		scanf(" %d",&b);
		
		v.push_back(make_pair(a,b));
		
		mep.insert(make_pair(make_pair(a,b),i));
	}
	
	sort(v.begin(),v.end());
	
	for(int i = 0; i < N; i++){
		vtemp.push_back(v[i]);
	}
	
	convex.push_back(vtemp[0]);
	vtemp.pop_front();
	
	convex.push_back(vtemp[0]);
	vtemp.pop_front();
	
	for(int i = 0; i < vtemp.size(); vtemp.pop_front()){
		while(convex.size() >= 2 && compare( m(convex[convex.size() - 2] , convex[convex.size() - 1]), m(convex[convex.size() - 2], vtemp.front())) ){
			vtap.push_back(convex[convex.size() - 1]);
			convex.pop_back();
		}
		convex.push_back(vtemp.front());
	}
	
	int t = convex.size();

	for(int i = 0; i < vtap.size(); vtap.pop_front()){
		while(convex.size() >= t + 1 && compare(m(convex[convex.size() - 2], vtap.front()),  m(convex[convex.size() - 2] , convex[convex.size() - 1])) ){
			vtemp.push_front(convex[convex.size() - 1]);
			convex.pop_back();
		}
		convex.push_back(vtap.front());
	}
	
	t = convex.size();
	
	for(int i = 0; i < vtemp.size(); vtemp.pop_front()){
		while(convex.size() >= t + 1 && compare( m(convex[convex.size() - 2] , convex[convex.size() - 1]), m(convex[convex.size() - 2], vtemp.front())) ){
			vtap.push_back(convex[convex.size() - 1]);
			convex.pop_back();
		}
		convex.push_back(vtemp.front());
	}
	
	t = convex.size();
	
	for(int i = 0; i < vtap.size(); vtap.pop_front()){
		while(convex.size() >= t + 1 && compare(m(convex[convex.size() - 2], vtap.front()),  m(convex[convex.size() - 2] , convex[convex.size() - 1])) ){
			convex.pop_back();
		}
		convex.push_back(vtap.front());
	}
	
	gloeb = 0;
	
	dfs(1,-1);
	
	for(int i = 0; i < N; i++){
		printf("%d",ans[i]);
		if(i != N -1 ){
			printf(" ");
		}
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0; i < vtemp.size(); vtemp.pop_front()){
      |                 ~~^~~~~~~~~~~~~~
Main.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i = 0; i < vtap.size(); vtap.pop_front()){
      |                 ~~^~~~~~~~~~~~~
Main.cpp:81:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |   while(convex.size() >= t + 1 && compare(m(convex[convex.size() - 2], vtap.front()),  m(convex[convex.size() - 2] , convex[convex.size() - 1])) ){
      |         ~~~~~~~~~~~~~~^~~~~~~~
Main.cpp:90:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int i = 0; i < vtemp.size(); vtemp.pop_front()){
      |                 ~~^~~~~~~~~~~~~~
Main.cpp:91:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |   while(convex.size() >= t + 1 && compare( m(convex[convex.size() - 2] , convex[convex.size() - 1]), m(convex[convex.size() - 2], vtemp.front())) ){
      |         ~~~~~~~~~~~~~~^~~~~~~~
Main.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 0; i < vtap.size(); vtap.pop_front()){
      |                 ~~^~~~~~~~~~~~~
Main.cpp:101:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |   while(convex.size() >= t + 1 && compare(m(convex[convex.size() - 2], vtap.front()),  m(convex[convex.size() - 2] , convex[convex.size() - 1])) ){
      |         ~~~~~~~~~~~~~~^~~~~~~~
Main.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf(" %d",&N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf(" %d",&a);
      |   ~~~~~^~~~~~~~~~
Main.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf(" %d",&b);
      |   ~~~~~^~~~~~~~~~
Main.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf(" %d",&a);
      |   ~~~~~^~~~~~~~~~
Main.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf(" %d",&b);
      |   ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 23096 KB Output is correct
2 Correct 300 ms 27464 KB Output is correct
3 Correct 250 ms 25628 KB Output is correct
4 Correct 335 ms 30144 KB Output is correct
5 Correct 226 ms 28776 KB Output is correct
6 Correct 240 ms 23080 KB Output is correct
7 Correct 222 ms 23812 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5588 KB Output is correct
2 Incorrect 8 ms 5660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5588 KB Output is correct
2 Incorrect 8 ms 5660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5588 KB Output is correct
2 Incorrect 8 ms 5660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 23096 KB Output is correct
2 Correct 300 ms 27464 KB Output is correct
3 Correct 250 ms 25628 KB Output is correct
4 Correct 335 ms 30144 KB Output is correct
5 Correct 226 ms 28776 KB Output is correct
6 Correct 240 ms 23080 KB Output is correct
7 Correct 222 ms 23812 KB Output is correct
8 Correct 10 ms 5588 KB Output is correct
9 Incorrect 8 ms 5660 KB Output isn't correct
10 Halted 0 ms 0 KB -