oj.uz

Submission #1062895

# Submission time Handle Problem Language Result Execution time Memory
1062895 2024-08-17T11:42:29 Z nightfal Stations (IOI20_stations) C++17
39 / 100
 651 ms 944 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,9)) return 4;
	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 labelSub1(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 labelSub2(int n, vector<int> &labels) {
	for(int i=0; i<n; i++) labels[i] = i+1;
}
void labelSub3(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 base, int offset, int order, vector<vector<int>> &g, vector<int> &labels) {
	if(labels[node]!=-1) return;
	labels[node] = base + offset*order;
	offset /= 10;
	for(int i=0; i<g[node].size(); i++)
		dfs(g[node][i],labels[node],offset,i+1,g,labels);
}
void labelSub4(vector<vector<int>> &g, vector<int> &labels) {
	dfs(0,0,pow(10,7),1,g,labels);
	// print(g);
	// 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: labelSub1(n,g,labels); return labels;
		case 2: labelSub2(n,labels); return labels;
		case 3: labelSub3(n,g,labels); return labels;
		case 4: labelSub4(g,labels); return labels;
	}
}
int findSubDecision(int s, int t, vector<int> &c) {
	if (s >= pow(10,7)) return 4;
	if (s >= 1'000 && t >= 1'000) return 3;
	for(int i=0; i<c.size(); i++)
		if (c[i] < s-1 || c[i] > s+1) return 2;
	return 1;
}
int findSub1(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 findSub2(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 findSub3(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) {
		if(s < t) { for(int elem: c) if(elem > s) return elem; }
		else { 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 findSub4(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 find_next_station(int s, int t, std::vector<int> c) {
	int subtask = findSubDecision(s,t,c);
	switch(subtask) {
		case 1: return findSub1(s,t,c);
		case 2: return findSub2(s,t,c);
		case 3: return findSub3(s,t,c);
		case 4: return findSub4(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 labelSub3(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, int, int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:56:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i=0; i<g[node].size(); i++)
      |               ~^~~~~~~~~~~~~~~
stations.cpp: In function 'int findSubDecision(int, int, std::vector<int>&)':
stations.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  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:65:25: warning: control reaches end of non-void function [-Wreturn-type]
   65 |  vector<vector<int>> g(n);
      |                         ^
stations.cpp: In function 'int findSub3(int, int, std::vector<int>&)':
stations.cpp:104:1: warning: control reaches end of non-void function [-Wreturn-type]
  104 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 684 KB Output is correct
2 Correct 295 ms 684 KB Output is correct
3 Correct 610 ms 684 KB Output is correct
4 Correct 473 ms 684 KB Output is correct
5 Correct 398 ms 684 KB Output is correct
6 Correct 274 ms 684 KB Output is correct
7 Correct 268 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 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 684 KB Output is correct
2 Correct 355 ms 684 KB Output is correct
3 Correct 651 ms 684 KB Output is correct
4 Correct 454 ms 684 KB Output is correct
5 Correct 447 ms 684 KB Output is correct
6 Correct 338 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 940 KB Output is correct
2 Correct 294 ms 684 KB Output is correct
3 Correct 601 ms 684 KB Output is correct
4 Correct 458 ms 684 KB Output is correct
5 Correct 418 ms 944 KB Output is correct
6 Correct 319 ms 684 KB Output is correct
7 Correct 293 ms 684 KB Output is correct
8 Correct 1 ms 776 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 0 ms 776 KB Output is correct
11 Correct 425 ms 776 KB Output is correct
12 Correct 314 ms 760 KB Output is correct
13 Correct 328 ms 772 KB Output is correct
14 Correct 302 ms 936 KB Output is correct
15 Correct 30 ms 736 KB Output is correct
16 Correct 31 ms 776 KB Output is correct
17 Correct 75 ms 744 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 684 KB Output is correct
2 Correct 464 ms 684 KB Output is correct
3 Correct 412 ms 684 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 417 ms 684 KB Output is correct
8 Correct 617 ms 684 KB Output is correct
9 Correct 480 ms 684 KB Output is correct
10 Correct 411 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 2 ms 772 KB Output is correct
13 Correct 3 ms 776 KB Output is correct
14 Correct 2 ms 764 KB Output is correct
15 Correct 0 ms 776 KB Output is correct
16 Correct 338 ms 684 KB Output is correct
17 Correct 354 ms 684 KB Output is correct
18 Correct 351 ms 684 KB Output is correct
19 Correct 364 ms 684 KB Output is correct
20 Correct 353 ms 684 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Invalid labels (duplicates values). scenario=1, label=12121212
2 Halted 0 ms 0 KB -