oj.uz

Submission #1059482

# Submission time Handle Problem Language Result Execution time Memory
1059482 2024-08-15T03:20:09 Z nightfal Stations (IOI20_stations) C++17
62.6795 / 100
 551 ms 1196 KB 
// #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,9)) return n<=8?  4:5;
	if (k==pow(10,9)) return 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) {
	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};
}
void labelsSubtask5(int n, vector<vector<int>> &g, vector<int> &labels) {
	int preNum=0, postNum=0, dNum=0;
	vector<int> pre(n,-1), post(n,-1), dist(n,-1);
	pporder(0,preNum,postNum,dNum,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] = pre[i]*1'000+post[i];
		labels[i] = pre[i]*1'000+post[i]+pow(10,6);
		// labels[i] = dist[i]%2? pre[i]+1000: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(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,6) || t>pow(10,6)) 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(int s, int t, vector<int> &c) {
	s %= (int) pow(10,7), t %= (int) pow(10,7);
	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++) { 
        int temp = c[i] % (int) pow(10,7); 
        pre[i] = temp/1'000; post[i] = temp%1'000; 
    }
	// 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(s,t,c);
	}
}

Compilation message

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:147:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |    for(int i=0; i<c.size(); i++)
      |                 ~^~~~~~~~~
stations.cpp: In function 'int findSubtask5(int, int, std::vector<int>&)':
stations.cpp:187:22: warning: unused variable 'postS' [-Wunused-variable]
  187 |  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:109:28: warning: control reaches end of non-void function [-Wreturn-type]
  109 |     vector<vector<int>> g(n);
      |                            ^
stations.cpp: In function 'int findSubtask1(int, int, std::vector<int>&)':
stations.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
  156 | }
      | ^
stations.cpp: In function 'int findSubtask5(int, int, std::vector<int>&)':
stations.cpp:190:19: warning: control reaches end of non-void function [-Wreturn-type]
  190 |  vector<int> pre(m), post(m);
      |                   ^
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:218:1: warning: control reaches end of non-void function [-Wreturn-type]
  218 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 944 KB Output is correct
2 Correct 255 ms 684 KB Output is correct
3 Correct 497 ms 684 KB Output is correct
4 Correct 353 ms 684 KB Output is correct
5 Correct 315 ms 684 KB Output is correct
6 Correct 230 ms 940 KB Output is correct
7 Correct 227 ms 688 KB Output is correct
8 Correct 0 ms 768 KB Output is correct
9 Correct 3 ms 780 KB Output is correct
10 Correct 1 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 684 KB Output is correct
2 Correct 289 ms 684 KB Output is correct
3 Correct 523 ms 684 KB Output is correct
4 Correct 365 ms 688 KB Output is correct
5 Correct 310 ms 684 KB Output is correct
6 Correct 263 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 684 KB Output is correct
2 Correct 255 ms 712 KB Output is correct
3 Correct 534 ms 684 KB Output is correct
4 Correct 377 ms 684 KB Output is correct
5 Correct 305 ms 684 KB Output is correct
6 Correct 274 ms 684 KB Output is correct
7 Correct 252 ms 684 KB Output is correct
8 Correct 2 ms 776 KB Output is correct
9 Correct 1 ms 776 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 359 ms 768 KB Output is correct
12 Correct 276 ms 764 KB Output is correct
13 Correct 237 ms 684 KB Output is correct
14 Correct 269 ms 684 KB Output is correct
15 Correct 22 ms 764 KB Output is correct
16 Correct 26 ms 684 KB Output is correct
17 Correct 67 ms 764 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 684 KB Output is correct
2 Correct 407 ms 684 KB Output is correct
3 Correct 360 ms 684 KB Output is correct
4 Correct 1 ms 776 KB Output is correct
5 Correct 1 ms 764 KB Output is correct
6 Correct 0 ms 764 KB Output is correct
7 Correct 346 ms 684 KB Output is correct
8 Correct 517 ms 684 KB Output is correct
9 Correct 373 ms 684 KB Output is correct
10 Correct 338 ms 684 KB Output is correct
11 Correct 3 ms 776 KB Output is correct
12 Correct 3 ms 776 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 1 ms 776 KB Output is correct
15 Correct 0 ms 776 KB Output is correct
16 Correct 270 ms 768 KB Output is correct
17 Correct 268 ms 684 KB Output is correct
18 Correct 288 ms 684 KB Output is correct
19 Correct 293 ms 684 KB Output is correct
20 Correct 271 ms 684 KB Output is correct

Subtask #5
23.6795 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 314 ms 940 KB Partially correct
2 Partially correct 297 ms 944 KB Partially correct
3 Partially correct 525 ms 684 KB Partially correct
4 Partially correct 375 ms 684 KB Partially correct
5 Partially correct 373 ms 684 KB Partially correct
6 Partially correct 268 ms 940 KB Partially correct
7 Partially correct 284 ms 684 KB Partially correct
8 Partially correct 1 ms 764 KB Partially correct
9 Partially correct 2 ms 768 KB Partially correct
10 Partially correct 0 ms 776 KB Partially correct
11 Partially correct 261 ms 684 KB Partially correct
12 Partially correct 304 ms 684 KB Partially correct
13 Partially correct 525 ms 936 KB Partially correct
14 Partially correct 415 ms 684 KB Partially correct
15 Partially correct 342 ms 684 KB Partially correct
16 Partially correct 255 ms 684 KB Partially correct
17 Partially correct 354 ms 684 KB Partially correct
18 Partially correct 254 ms 756 KB Partially correct
19 Partially correct 264 ms 1036 KB Partially correct
20 Partially correct 249 ms 684 KB Partially correct
21 Partially correct 33 ms 768 KB Partially correct
22 Partially correct 29 ms 688 KB Partially correct
23 Partially correct 56 ms 736 KB Partially correct
24 Partially correct 2 ms 764 KB Partially correct
25 Partially correct 2 ms 776 KB Partially correct
26 Partially correct 1 ms 768 KB Partially correct
27 Partially correct 1 ms 764 KB Partially correct
28 Partially correct 0 ms 768 KB Partially correct
29 Partially correct 263 ms 684 KB Partially correct
30 Partially correct 293 ms 684 KB Partially correct
31 Partially correct 285 ms 684 KB Partially correct
32 Partially correct 333 ms 688 KB Partially correct
33 Partially correct 306 ms 684 KB Partially correct
34 Partially correct 154 ms 684 KB Partially correct
35 Partially correct 220 ms 1032 KB Partially correct
36 Partially correct 243 ms 1196 KB Partially correct
37 Partially correct 248 ms 1028 KB Partially correct
38 Partially correct 278 ms 932 KB Partially correct
39 Partially correct 263 ms 940 KB Partially correct
40 Partially correct 266 ms 684 KB Partially correct
41 Partially correct 279 ms 932 KB Partially correct
42 Partially correct 26 ms 764 KB Partially correct
43 Partially correct 48 ms 684 KB Partially correct
44 Partially correct 69 ms 744 KB Partially correct
45 Partially correct 76 ms 716 KB Partially correct
46 Partially correct 179 ms 684 KB Partially correct
47 Partially correct 186 ms 684 KB Partially correct
48 Partially correct 32 ms 1004 KB Partially correct
49 Partially correct 36 ms 844 KB Partially correct