oj.uz

Submission #1062402

# Submission time Handle Problem Language Result Execution time Memory
1062402 2024-08-17T06:13:11 Z nightfal Stations (IOI20_stations) C++17
29 / 100
 645 ms 1016 KB 
#include <vector>
#include <iostream>
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) {
	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;
	}
	return;
}
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;

	labelLine(0,node,g,labels);
	return;
}
void labelSub2(int n, vector<int> &labels) {
	for(int i=0; i<n; i++)
		labels[i] = i+1;
	return;
}
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++)
		labelLine((i+1)*1'000+1,g[root][i],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);
	// print(g);
	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;
	}
}
int findSubDecision(int s, int t, vector<int> &c) {
	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) {
	for(int i=c.size()-1; i>=0; i--)
		if(ancestor(c[i],t)) return c[i];
	return c[0];
}
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;
	}
}
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);
	}
	return c[0];
}

Compilation message

stations.cpp: In function 'void makeG(std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
stations.cpp:10:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  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:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0; i<u.size(); i++)
      |               ~^~~~~~~~~
stations.cpp:23:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   23 |   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:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i=0; i<g[root].size(); i++)
      |               ~^~~~~~~~~~~~~~~
stations.cpp: In function 'int findSubDecision(int, int, std::vector<int>&)':
stations.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  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:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:58:25: warning: control reaches end of non-void function [-Wreturn-type]
   58 |  vector<vector<int>> g(n);
      |                         ^
stations.cpp: In function 'int findSub3(int, int, std::vector<int>&)':
stations.cpp:108:1: warning: control reaches end of non-void function [-Wreturn-type]
  108 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 684 KB Output is correct
2 Correct 305 ms 684 KB Output is correct
3 Correct 633 ms 940 KB Output is correct
4 Correct 425 ms 944 KB Output is correct
5 Correct 396 ms 684 KB Output is correct
6 Correct 301 ms 684 KB Output is correct
7 Correct 304 ms 684 KB Output is correct
8 Correct 2 ms 764 KB Output is correct
9 Correct 1 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 298 ms 684 KB Output is correct
2 Correct 377 ms 684 KB Output is correct
3 Correct 583 ms 684 KB Output is correct
4 Correct 466 ms 944 KB Output is correct
5 Correct 415 ms 684 KB Output is correct
6 Correct 280 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 684 KB Output is correct
2 Correct 292 ms 940 KB Output is correct
3 Correct 577 ms 684 KB Output is correct
4 Correct 442 ms 684 KB Output is correct
5 Correct 364 ms 684 KB Output is correct
6 Correct 306 ms 684 KB Output is correct
7 Correct 294 ms 684 KB Output is correct
8 Correct 1 ms 772 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 764 KB Output is correct
11 Correct 416 ms 768 KB Output is correct
12 Correct 314 ms 1016 KB Output is correct
13 Correct 315 ms 932 KB Output is correct
14 Correct 321 ms 684 KB Output is correct
15 Correct 27 ms 768 KB Output is correct
16 Correct 32 ms 684 KB Output is correct
17 Correct 54 ms 760 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 684 KB Output is correct
2 Correct 459 ms 688 KB Output is correct
3 Correct 410 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 776 KB Output is correct
7 Correct 414 ms 684 KB Output is correct
8 Correct 584 ms 684 KB Output is correct
9 Correct 466 ms 684 KB Output is correct
10 Correct 386 ms 684 KB Output is correct
11 Incorrect 0 ms 344 KB Invalid labels (values out of range). scenario=5, k=1000000000, vertex=4, label=-1
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 684 KB Output is correct
2 Correct 277 ms 684 KB Output is correct
3 Correct 645 ms 684 KB Output is correct
4 Correct 482 ms 684 KB Output is correct
5 Correct 419 ms 684 KB Output is correct
6 Correct 290 ms 684 KB Output is correct
7 Correct 305 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 1 ms 776 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 321 ms 768 KB Output is correct
12 Correct 373 ms 944 KB Output is correct
13 Correct 613 ms 684 KB Output is correct
14 Correct 471 ms 684 KB Output is correct
15 Correct 376 ms 684 KB Output is correct
16 Correct 301 ms 688 KB Output is correct
17 Partially correct 446 ms 684 KB Partially correct
18 Partially correct 334 ms 932 KB Partially correct
19 Partially correct 355 ms 760 KB Partially correct
20 Partially correct 321 ms 684 KB Partially correct
21 Partially correct 27 ms 768 KB Partially correct
22 Partially correct 47 ms 764 KB Partially correct
23 Partially correct 57 ms 772 KB Partially correct
24 Incorrect 0 ms 344 KB Invalid labels (values out of range). scenario=5, k=1000000000, vertex=1, label=-1
25 Halted 0 ms 0 KB -