Submission #1055890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055890		nightfal	Stations (IOI20_stations)	C++17	0 / 100	505 ms	684 KiB

stations

// #include "stations.h"
#include <cstdio>
#include <iostream>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;


template <typename T> void print(T elem) {cout << elem << " ";}
template <typename T> void print(vector<T> &v) {for(auto elem: v) print(elem); cout << endl;};
template <typename T> void print(vector<vector<T>> &v) {for(auto elem: v) print(elem); cout << endl;};

int DecideLabelsSubtask(int n, int k, vector<vector<int>> &g, vector<int> &u, vector<int> &v) {
	if (k==pow(10,9)) return n<=8?  4:5;
	else if (k>pow(10,3)) return 3;
	for(auto elem: g) 
		if(elem.size()>2) return 2;
	return 1;
}
void labelsSubtask1(int n, vector<vector<int>> &g, vector<int> &labels) {
	int node = 0;
	for (int i=0; i<n; i++)
		if(g[i].size()==1) node = i;

	for (int i=0; i<n; i++) {
		labels[node] = i;
		for(int child: g[node])
			if(labels[child]== -1) {node = child;}
	}
	return;
}
void labelsSubtask2(int n, vector<int> &labels) {
	for(int i=0; i<n; i++)
		labels[i] = i;
	return;
}
void genLabels3(int key, int node, vector<vector<int>> &g, vector<int> &labels) {
    labels[node]=key*1000+1;
    for(int i=2; i<1000; i++) {
        bool terminal = true;
        for(int child: g[node]) {
            if(labels[child]==-1) {labels[child] = 1000*key+i; node = child; terminal=false;}
        }
        if (terminal) return;
    }
}
void labelsSubtask3(int n, vector<vector<int>> &g, vector<int> &labels) {
	int root = 0;
	for(int i=0; i<n; i++)
		if(g[i].size() > 2)  {root = i; break;}
	labels[root] = 1000;
	for(int i=0; i<g[root].size(); i++) {
		int child = g[root][i];
		genLabels3(i+1, child, g, labels);
	} 
	return;
}
void genLabels4(int base, int key, int exp, int node, vector<vector<int>> &g, vector<int> &labels) {
    labels[node]=base + key*pow(10,exp);
	base = labels[node];

    for(int i=0; i<g[node].size(); i++) {
		int child = g[node][i];
		if (labels[child]==-1) 
        	genLabels4(base,i+1,exp-1, child, g, labels);
    }
	return;
}
void labelsSubtask4(int n, vector<vector<int>> &g, vector<int> &labels) {
	labels[0] = pow(10,8);
	int base = labels[0];
	for(int i=0; i<g[0].size(); i++) {
		int child = g[0][i];
		if (labels[child]==-1) 
			genLabels4(base,i+1,7, child, g, labels);
	}	
}
void postorder(int node, int &order, vector<vector<int>> &g, vector<int> &labels, vector<bool> &visit) {
	if (visit[node]) return;
	visit[node] = true;
	for(int child: g[node])
		postorder(child,order,g,labels,visit);
	labels[node] = order++;
	return;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n,-1);
    vector<vector<int>> g(n);
    for (int i=0; i<n-1; i++) {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
	int order = 0;
	vector<bool> visit(n);
	postorder(0, order, g, labels,visit);
	// print(g);
    // print(labels);
	return labels;

	int subtask = DecideLabelsSubtask(n,k,g,u,v);
	switch(subtask) {
		case 1: labelsSubtask1(n, g, labels); break;
    	case 2: labelsSubtask2(n,labels); break;
		case 3: labelsSubtask3(n,g,labels); break;
		case 4: labelsSubtask4(n,g,labels);
	}
	return labels;
}
bool ancestor(int s, int t) {
    if (s==0) return true;
    while (t) {
        if (s==t) return true;
        t = (t-1)>>1;
    }
    return false;
}
int decideFindSubtask(int s, int t, vector<int> &c) {
	if (s>pow(10,8) || t>pow(10,8)) return 4;
    else if (s>1'000 || t>1'000) return 3;
	switch(s) {
		case 0:
			if (c.size()==1) return 1;
			else if (c.size()==2) return 2;
		case 1:
			if (t==0) return -1;
			else {
				for(int elem: c) 
					if(elem > 2) return 2;
				return 1;
			}
		default:
			for(int i=0; i<c.size(); i++)
				if(!(c[i]==s-1 || c[i]==s+1)) return 2;
			return 1;
	}
}
int find_next_station(int s, int t, std::vector<int> c) {
	
	// fulltask
	for(int i=0; i<c.size(); i++)
		if(c[i]>=t) return c[i];
	return c[c.size()-1];

    int subtask = decideFindSubtask(s,t,c);
	switch(subtask) {
		case -1: return 0;
		case 1: 
	        for(int child: c)
    	        if (s<t && s<child) return child;
        	    else if (s>t && s>child) return child;
		case 2:
	        if (ancestor(2*s+1,t)) return 2*s+1;
    	    else if (ancestor(2*s+2,t)) return 2*s+2;
        	else return (s-1)/2;
		case 3:
			if (s==1000) return (t/1000)*1000+1;
			else if (s/1000 == t/1000) {
				if (s<t) return s+1;
				else return s-1;
			}
			else { 
				if (s%1000==1) return 1000;
				else return s-1;
			}
		case 4: 
			int sZeros=0, tZeros=0, s2=s, t2=t;
			while (s2%10==0) {s2/=10; sZeros++;}
			while (t2%10==0) {t2/=10; tZeros++;}
			if(sZeros>tZeros) {
				for(int i=0; i<sZeros-tZeros; i++) t2/=10;
				int divisor = pow(10,sZeros-1);
				if (s2==t2) {return (t/divisor)*divisor;}
			}
			int divisor = pow(10,sZeros+1);
			return (s/divisor)*divisor;
	}
}

Compilation message (stderr)

stations.cpp: In function 'void labelsSubtask3(int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i=0; i<g[root].size(); i++) {
      |               ~^~~~~~~~~~~~~~~
stations.cpp: In function 'void genLabels4(int, int, int, int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0; i<g[node].size(); i++) {
      |                  ~^~~~~~~~~~~~~~~
stations.cpp: In function 'void labelsSubtask4(int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:75:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i=0; i<g[0].size(); i++) {
      |               ~^~~~~~~~~~~~
stations.cpp: In function 'int decideFindSubtask(int, int, std::vector<int>&)':
stations.cpp:135:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |    for(int i=0; i<c.size(); i++)
      |                 ~^~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:143:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |  for(int i=0; i<c.size(); i++)
      |               ~^~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61