oj.uz

Submission #1063119

# Submission time Handle Problem Language Result Execution time Memory
1063119 2024-08-17T14:24:01 Z nightfal Stations (IOI20_stations) C++17
44.0422 / 100
 646 ms 1392 KB 
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
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;}

void makeG(vector<vector<int>> &g, vector<int> &u, vector<int> &v) {
	for(int i=0; i<u.size(); i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
}
int labelSubDecision(int n, int k, vector<vector<int>> &g, vector<int> &u, vector<int> &v) {
	if (k>=pow(10,6)) return 5;
	int cnt = 0;
	for(int i=0; i<n; i++) if (g[i].size()>2) cnt++;
	if (cnt==0) return 1;

	bool subtask2 = true;
	for(int i=0; i<u.size(); i++)
		if (!(u[i]==i+1 && v[i]==i/2 || u[i]==i/2 && v[i]==i+1)) subtask2= false;
	if (subtask2) return 2;
	if (cnt==1) return 3;
}
void labelLine(int cnt, int node, vector<vector<int>> &g, vector<int> &labels) {
	while(labels[node]==-1) {
		labels[node] = cnt++;
		for(int elem: g[node]) if (labels[elem]==-1) node = elem;
	}
}
void label1(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; break;}
	labelLine(0,node,g,labels);
}
void label2(int n, vector<int> &labels) {
	for(int i=0; i<n; i++) labels[i] = i+1;
}
void label3(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] = 1'000;
	for(int i=0; i<g[root].size(); i++) {
		int child = g[root][i];
		labelLine((i+1)*1'000+1,child,g,labels);
	}
}
void dfs(int node, int offset, vector<vector<int>> &g, vector<int> &labels) {
	for(int i=0; i<g[node].size(); i++) {
		int child = g[node][i];
		if(labels[child]!=-1) continue;
		labels[child] = labels[node] + offset*(i+1);
		dfs(child,offset/10,g,labels);
	}
}
void label4(vector<vector<int>> &g, vector<int> &labels) {
	labels[0] = pow(10,7);
	dfs(0,pow(10,6),g,labels);
}
int dfs2(int node, int cnt, vector<vector<int>> &g, vector<int> &pre, vector<int> &post) {
	if (pre[node]!=-1) return cnt;
	pre[node] = cnt++;
	for(int child: g[node])
		cnt = dfs2(child,cnt,g,pre,post);
	post[node] = cnt++;
	return cnt;
}
void label5(int n, vector<vector<int>> &g, vector<int> &labels) {
	vector<int> pre(n,-1), post(n,-1);
	dfs2(0,0,g,pre,post);
	for(int i=0; i<n; i++)
		labels[i] = pre[i]*2000 + post[i];
	// print(labels);
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<vector<int>> g(n);
	makeG(g,u,v);
	int subtask = labelSubDecision(n,k,g,u,v);
	vector<int> labels(n,-1);
	switch(subtask) {
		case 1: label1(n,g,labels); return labels;
		case 2: label2(n,labels); return labels;
		case 3: label3(n,g,labels); return labels;
		case 4: label4(g,labels); return labels;
		case 5: label5(n,g,labels); return labels;
	}
}
int findSubDecision(int s, int t, vector<int> &c) {
	// if (s >= pow(10,7)) return 4;
	if (s >= 2'000 || t >= 2'000) return 5;
	for(int i=0; i<c.size(); i++)
		if (c[i] < s-1 || c[i] > s+1) return 2;
	return 1;
}
int find1(int s, int t, vector<int> &c) {
	if (c.size()==1) return c[0];
	else return t<s? c[0]:c[1];
}
bool ancestor(int a, int b) {
	if (a==0) return true;
	while(b!=0) { if(a==b) return true; else b >>= 1; }
	return false;
}
int find2(int s, int t, vector<int> &c) {
	reverse(c.begin(),c.end());
	for(int elem: c) if(ancestor(elem,t)) return elem;
	return c[c.size()-1];
}
int find3(int s, int t, vector<int> &c) {
	if (s==1'000) { for(int elem: c) if(t/1000==elem/1000) return elem; }
	else if (s/1000 == t/1000 && s < t) { for(int elem: c) if(elem > s) return elem; }
	else { for(int elem: c) if(elem < s) return elem; }
}
bool ancestor4(int a, int b) {
	int divisor = 1;
	for(int i=0; i<=7; i++) {
		if (b - b % divisor == a) return true;
		divisor *= 10;
	}
	return false;
}
int find4(int s, int t, vector<int> &c) {
	reverse(c.begin(),c.end());
	for(int elem: c) if(ancestor4(elem,t)) return elem;
	return c[c.size()-1];
}
int find5(int s, int t, vector<int> &c) {
	int preS = s/2000, postS = s%2000;
	int preT = t/2000, postT = t%2000;
	int m = c.size();
	// cout << "s:" << s << " t:" << t<< endl;

	if (preT < preS || postS < postT) return c[0];
	else {
		for(int i=1; i<m; i++) 
			if(preT < c[i]/2000) return c[i-1];
		return c[m-1];
	}
}
int find_next_station(int s, int t, std::vector<int> c) {
	int subtask = findSubDecision(s,t,c);
	switch(subtask) {
		case 1: return find1(s,t,c);
		case 2: return find2(s,t,c);
		case 3: return find3(s,t,c);
		case 4: return find4(s,t,c);
		case 5: return find5(s,t,c);
	}
	return c[0];
}

Compilation message

stations.cpp: In function 'void makeG(std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
stations.cpp:12:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i=0; i<u.size(); i++) {
      |               ~^~~~~~~~~
stations.cpp: In function 'int labelSubDecision(int, int, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
stations.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i=0; i<u.size(); i++)
      |               ~^~~~~~~~~
stations.cpp:25:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   25 |   if (!(u[i]==i+1 && v[i]==i/2 || u[i]==i/2 && v[i]==i+1)) subtask2= false;
stations.cpp: In function 'void label3(int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=0; i<g[root].size(); i++) {
      |               ~^~~~~~~~~~~~~~~
stations.cpp: In function 'void dfs(int, int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i=0; i<g[node].size(); i++) {
      |               ~^~~~~~~~~~~~~~~
stations.cpp: In function 'int findSubDecision(int, int, std::vector<int>&)':
stations.cpp:95:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for(int i=0; i<c.size(); i++)
      |               ~^~~~~~~~~
stations.cpp: In function 'int labelSubDecision(int, int, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
stations.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
   28 | }
      | ^
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:80:25: warning: control reaches end of non-void function [-Wreturn-type]
   80 |  vector<vector<int>> g(n);
      |                         ^
stations.cpp: In function 'int find3(int, int, std::vector<int>&)':
stations.cpp:117:1: warning: control reaches end of non-void function [-Wreturn-type]
  117 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 684 KB Output is correct
2 Correct 316 ms 684 KB Output is correct
3 Correct 610 ms 684 KB Output is correct
4 Correct 442 ms 684 KB Output is correct
5 Correct 370 ms 684 KB Output is correct
6 Correct 317 ms 688 KB Output is correct
7 Correct 302 ms 684 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 0 ms 1268 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 684 KB Output is correct
2 Correct 401 ms 684 KB Output is correct
3 Correct 603 ms 680 KB Output is correct
4 Correct 434 ms 684 KB Output is correct
5 Correct 408 ms 684 KB Output is correct
6 Correct 308 ms 936 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Invalid labels (values out of range). scenario=1, k=1000000, vertex=3, label=1157149
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 876 KB Output is correct
2 Correct 434 ms 684 KB Output is correct
3 Correct 378 ms 688 KB Output is correct
4 Correct 1 ms 764 KB Output is correct
5 Correct 2 ms 776 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 381 ms 684 KB Output is correct
8 Correct 646 ms 684 KB Output is correct
9 Correct 516 ms 684 KB Output is correct
10 Correct 385 ms 684 KB Output is correct
11 Correct 2 ms 772 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Correct 3 ms 776 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 308 ms 772 KB Output is correct
17 Correct 304 ms 684 KB Output is correct
18 Correct 337 ms 680 KB Output is correct
19 Correct 315 ms 684 KB Output is correct
20 Correct 378 ms 684 KB Output is correct

Subtask #5
21.0422 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 380 ms 684 KB Partially correct
2 Partially correct 289 ms 684 KB Partially correct
3 Partially correct 618 ms 688 KB Partially correct
4 Partially correct 445 ms 684 KB Partially correct
5 Partially correct 366 ms 684 KB Partially correct
6 Partially correct 283 ms 684 KB Partially correct
7 Partially correct 315 ms 684 KB Partially correct
8 Partially correct 1 ms 772 KB Partially correct
9 Partially correct 1 ms 764 KB Partially correct
10 Partially correct 1 ms 776 KB Partially correct
11 Partially correct 293 ms 684 KB Partially correct
12 Partially correct 397 ms 684 KB Partially correct
13 Partially correct 583 ms 684 KB Partially correct
14 Partially correct 484 ms 688 KB Partially correct
15 Partially correct 405 ms 684 KB Partially correct
16 Partially correct 288 ms 684 KB Partially correct
17 Partially correct 394 ms 680 KB Partially correct
18 Partially correct 330 ms 1012 KB Partially correct
19 Partially correct 301 ms 684 KB Partially correct
20 Partially correct 298 ms 684 KB Partially correct
21 Partially correct 32 ms 768 KB Partially correct
22 Partially correct 48 ms 716 KB Partially correct
23 Partially correct 59 ms 768 KB Partially correct
24 Partially correct 3 ms 764 KB Partially correct
25 Partially correct 2 ms 764 KB Partially correct
26 Partially correct 4 ms 768 KB Partially correct
27 Partially correct 2 ms 776 KB Partially correct
28 Partially correct 0 ms 760 KB Partially correct
29 Partially correct 342 ms 688 KB Partially correct
30 Partially correct 358 ms 684 KB Partially correct
31 Partially correct 365 ms 684 KB Partially correct
32 Partially correct 339 ms 684 KB Partially correct
33 Partially correct 347 ms 684 KB Partially correct
34 Partially correct 208 ms 684 KB Partially correct
35 Partially correct 305 ms 684 KB Partially correct
36 Partially correct 299 ms 684 KB Partially correct
37 Partially correct 327 ms 1020 KB Partially correct
38 Partially correct 331 ms 932 KB Partially correct
39 Partially correct 303 ms 764 KB Partially correct
40 Partially correct 345 ms 936 KB Partially correct
41 Partially correct 324 ms 1392 KB Partially correct
42 Partially correct 39 ms 1024 KB Partially correct
43 Partially correct 66 ms 684 KB Partially correct
44 Partially correct 92 ms 688 KB Partially correct
45 Partially correct 100 ms 688 KB Partially correct
46 Partially correct 189 ms 684 KB Partially correct
47 Partially correct 176 ms 684 KB Partially correct
48 Partially correct 34 ms 820 KB Partially correct
49 Partially correct 44 ms 840 KB Partially correct