oj.uz

Submission #1062916

# Submission time Handle Problem Language Result Execution time Memory
1062916 2024-08-17T11:52:32 Z nightfal Stations (IOI20_stations) C++17
39 / 100
 619 ms 1016 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 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 labelSub4(vector<vector<int>> &g, vector<int> &labels) {
	labels[0] = pow(10,7);
	dfs(0,pow(10,6),g,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, 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: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 367 ms 684 KB Output is correct
2 Correct 302 ms 684 KB Output is correct
3 Correct 610 ms 684 KB Output is correct
4 Correct 442 ms 940 KB Output is correct
5 Correct 384 ms 684 KB Output is correct
6 Correct 293 ms 684 KB Output is correct
7 Correct 316 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 0 ms 776 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 684 KB Output is correct
2 Correct 360 ms 704 KB Output is correct
3 Correct 619 ms 684 KB Output is correct
4 Correct 355 ms 684 KB Output is correct
5 Correct 349 ms 684 KB Output is correct
6 Correct 306 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 684 KB Output is correct
2 Correct 292 ms 684 KB Output is correct
3 Correct 599 ms 684 KB Output is correct
4 Correct 407 ms 684 KB Output is correct
5 Correct 430 ms 684 KB Output is correct
6 Correct 300 ms 940 KB Output is correct
7 Correct 322 ms 684 KB Output is correct
8 Correct 2 ms 1016 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 379 ms 684 KB Output is correct
12 Correct 284 ms 848 KB Output is correct
13 Correct 292 ms 768 KB Output is correct
14 Correct 267 ms 684 KB Output is correct
15 Correct 31 ms 768 KB Output is correct
16 Correct 38 ms 764 KB Output is correct
17 Correct 62 ms 744 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 684 KB Output is correct
2 Correct 450 ms 772 KB Output is correct
3 Correct 367 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 3 ms 804 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 377 ms 772 KB Output is correct
8 Correct 557 ms 684 KB Output is correct
9 Correct 424 ms 684 KB Output is correct
10 Correct 404 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 3 ms 776 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 319 ms 684 KB Output is correct
17 Correct 344 ms 684 KB Output is correct
18 Correct 332 ms 684 KB Output is correct
19 Correct 301 ms 684 KB Output is correct
20 Correct 326 ms 776 KB Output is correct

Subtask #5
0 / 61.0

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