Submission #1060413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060413		nightfal	Stations (IOI20_stations)	C++17	65.32 / 100	622 ms	1444 KiB

stations

// #include "stations.h"
#include <cstdio>
#include <iostream>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
#include <tuple>
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,6)) return 5;
	// 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<vector<int>> &g, 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);
	}	
}
pair<int,int> pporder(int node, int preNum, int postNum, int dNum, vector<vector<int>> &g, 
						vector<int> &pre, vector<int> &post, vector<int> &dist) {
    if (pre[node]!=-1) return {preNum,postNum};
	pre[node] = preNum++;
	dist[node] = dNum++;
	for(int child: g[node])
		// if (pre[child]==-1)
			tie(preNum, postNum) = pporder(child,preNum,postNum,dNum,g,pre,post,dist);
	post[node] = postNum++;
	return {preNum,postNum};
}
int dfs(int node, int orderNum, int dNum, vector<vector<int>> &g, 
						vector<int> &pre, vector<int> &post, vector<int> &dist) {
    if (pre[node]!=-1) return orderNum;
	pre[node] = orderNum++;
	dist[node] = dNum++;
	for(int child: g[node])
		// if (pre[child]==-1)
			orderNum = dfs(child,orderNum,dNum,g,pre,post,dist);
	post[node] = orderNum++;
	return orderNum;
}
void labelsSubtask5_65(int n, vector<vector<int>> &g, vector<int> &labels) {
	vector<int> pre(n,-1), post(n,-1), dist(n,-1);
	pporder(0,0,0,0,g,pre,post,dist);
	for(int i=0; i<n; i++)
		labels[i] = pre[i]*1'000+post[i];
}
void labelsSubtask5_90(int n, vector<vector<int>> &g, vector<int> &labels) {
	vector<int> pre(n,-1), post(n,-1), dist(n,-1);
	dfs(0,0,0,g,pre,post,dist);
	// cout << "pre: "; print(pre); 
	// cout << "post: "; print(post);
	// cout << "dist: "; print(dist);
	for(int i=0; i<n; i++)
		labels[i] = dist[i]%2? pre[i]:post[i];
	// cout << "labels: "; print(labels);
}
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 subtask = DecideLabelsSubtask(n,k,g,u,v);
	switch(subtask) {
		case 1: labelsSubtask1(n,g,labels); return labels;
    	case 2: labelsSubtask2(n,g,labels); return labels;
		case 3: labelsSubtask3(n,g,labels); return labels;
		case 4: labelsSubtask4(n,g,labels); return labels;
		// case 5: labelsSubtask5_90(n,g,labels); return labels;
		case 5: labelsSubtask5_65(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;
	if (s>=pow(10,3) || t>=pow(10,3)) return 5;
    // else if (s>pow(10,3) || t>pow(10,3)) 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 findSubtask1(int s, int t, vector<int> &c) {
	for(int child: c)
		if (s<t && s<child) return child;
		else if (s>t && s>child) return child;
}
int findSubtask2(int s, int t, vector<int> &c) {
	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;
}
int findSubtask3(int s, int t, vector<int> &c) {
	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;
	}
}
int findSubtask4(int s, int t, vector<int> &c) {
	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;
}
int findSubtask5_65(int s, int t, vector<int> &c) {
	int preS = s/1'000, postS = s%1'000;
	int preT = t/1'000, postT = t%1'000;
	int m = c.size();
	vector<int> pre(m), post(m);
	for(int i=0; i<m; i++) { 
        pre[i] = c[i]/1'000; post[i] = c[i]%1'000; 
    }
	if(preS < pre[0]) { // s is the root.
		for(int i=0; i<m; i++)
			if(postT<=post[i]) {return c[i];}
	}
	else {  // s is an intermediate node.
		if(preT < preS)  {return c[0];}
		for(int i=1; i<m; i++)
			if(postT<=post[i])  {return c[i];}
		return c[0];
	}
}
int findSubtask5_90(int s, int t, vector<int> &c) {
	int m = c.size();
	vector<int> pre(m,-1), post(m,-1);
    if (s>=1000) { // s is preordered and c[i] is postordered.
        s -= 1000;
	    for(int i=0; i<m; i++) 
            post[i] = c[i];
        if(s==0) { // s is the root.
            if (t>1000) t -= 1000; // t is preordered.
            for(int i=0; i<m; i++)
                if(t<=post[i]+1) return c[i];
        }
        else { // s is an intermediate node.
            if (t>=1000) {  // t is preordered.
                t -= 1000;
                if (t<s) return c[m-1];
                for(int i=0; i<m-1; i++)
                    if(t<=post[i]) return c[i];            
                return c[m-1];
            }
            else { // t is postordered.
                if (t<s) return c[m-1];
                for(int i=0; i<m-1; i++)
                    if(t<=post[i]) return c[i]; 
                return c[m-1];
            }
        }
    }
    else {
        for(int i=0; i<m; i++) 
            pre[i] = c[i];
    }
	// cout << "pre: "; print(pre);
	// cout << "post: "; print(post);
	// if(preS < pre[0]) { // s is the root.
	// 	for(int i=0; i<m; i++)
	// 		if(postT<=post[i]) {return c[i];}
	// }
	// else {  // s is an intermediate node.
	// 	if(preT < preS)  {return c[0];}
	// 	for(int i=1; i<m; i++)
	// 		if(postT<=post[i])  {return c[i];}
	// 	return c[0];
	// }
}
int find_next_station(int s, int t, std::vector<int> c) {
    int subtask = decideFindSubtask(s,t,c);
	switch(subtask) {
		case -1: return 0;
		case 1: return findSubtask1(s,t,c);
		case 2: return findSubtask2(s,t,c);
		case 3: return findSubtask3(s,t,c);
		case 4: return findSubtask4(s,t,c);
		// case 5: return findSubtask5_90(s,t,c);
		case 5: return findSubtask5_65(s,t,c);
	}
}

Compilation message (stderr)

stations.cpp: In function 'void labelsSubtask3(int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  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:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     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:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i=0; i<g[0].size(); i++) {
      |               ~^~~~~~~~~~~~
stations.cpp: In function 'int decideFindSubtask(int, int, std::vector<int>&)':
stations.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |    for(int i=0; i<c.size(); i++)
      |                 ~^~~~~~~~~
stations.cpp: In function 'int findSubtask5_65(int, int, std::vector<int>&)':
stations.cpp:202:22: warning: unused variable 'postS' [-Wunused-variable]
  202 |  int preS = s/1'000, postS = s%1'000;
      |                      ^~~~~
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:124:28: warning: control reaches end of non-void function [-Wreturn-type]
  124 |     vector<vector<int>> g(n);
      |                            ^
stations.cpp: In function 'int findSubtask1(int, int, std::vector<int>&)':
stations.cpp:172:1: warning: control reaches end of non-void function [-Wreturn-type]
  172 | }
      | ^
stations.cpp: In function 'int findSubtask5_65(int, int, std::vector<int>&)':
stations.cpp:205:19: warning: control reaches end of non-void function [-Wreturn-type]
  205 |  vector<int> pre(m), post(m);
      |                   ^
stations.cpp: In function 'int findSubtask5_90(int, int, std::vector<int>&)':
stations.cpp:222:22: warning: control reaches end of non-void function [-Wreturn-type]
  222 |  vector<int> pre(m,-1), post(m,-1);
      |                      ^
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:276:1: warning: control reaches end of non-void function [-Wreturn-type]
  276 | }
      | ^

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