oj.uz

Submission #1062291

# Submission time Handle Problem Language Result Execution time Memory
1062291 2024-08-17T01:48:45 Z nightfal Stations (IOI20_stations) C++17
13 / 100
 626 ms 776 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 decideSubtaskLabel(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 subtask1Label(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;

	int cnt = 0;
	while(labels[node]==-1) {
		labels[node] = cnt++; 
		for(int elem: g[node])
			if(labels[elem]==-1) node = elem;
	}
	return;
}
void subtask2Label(int n, vector<int> &labels) {
	for(int i=0; i<n; i++)
		labels[i] = i+1;
	return;
}
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 = decideSubtaskLabel(n,k,g,u,v);
	vector<int> labels(n,-1);
	switch(subtask) {
		case 1: subtask1Label(n,g,labels); return labels;
		case 2: subtask2Label(n,labels); return labels;
		// case 2: 
		// case 3:
	}
}
int decideSubtaskFind(int s, int t, vector<int> &c) {

	for(int i=0; i<c.size(); i++)
		if (c[i] < s-1 || c[i] > s+1) return 2;
	return 1;
}
int subtask1Find(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 subtask2Find(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 find_next_station(int s, int t, std::vector<int> c) {
	int subtask = decideSubtaskFind(s,t,c);
	switch(subtask) {
		case 1: return subtask1Find(s,t,c);
		case 2: return subtask2Find(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 decideSubtaskLabel(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 'int decideSubtaskFind(int, int, std::vector<int>&)':
stations.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0; i<c.size(); i++)
      |               ~^~~~~~~~~
stations.cpp: In function 'int decideSubtaskLabel(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:47:25: warning: control reaches end of non-void function [-Wreturn-type]
   47 |  vector<vector<int>> g(n);
      |                         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 684 KB Output is correct
2 Correct 335 ms 684 KB Output is correct
3 Correct 594 ms 684 KB Output is correct
4 Correct 448 ms 684 KB Output is correct
5 Correct 411 ms 684 KB Output is correct
6 Correct 278 ms 688 KB Output is correct
7 Correct 323 ms 684 KB Output is correct
8 Correct 1 ms 772 KB Output is correct
9 Correct 1 ms 776 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 302 ms 684 KB Output is correct
2 Correct 355 ms 684 KB Output is correct
3 Correct 614 ms 684 KB Output is correct
4 Correct 448 ms 684 KB Output is correct
5 Correct 400 ms 684 KB Output is correct
6 Correct 286 ms 684 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 684 KB Output is correct
2 Correct 294 ms 680 KB Output is correct
3 Correct 590 ms 684 KB Output is correct
4 Correct 450 ms 684 KB Output is correct
5 Correct 358 ms 684 KB Output is correct
6 Correct 290 ms 684 KB Output is correct
7 Correct 291 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 0 ms 776 KB Output is correct
11 Runtime error 1 ms 344 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 692 KB Output is correct
2 Correct 446 ms 684 KB Output is correct
3 Correct 416 ms 696 KB Output is correct
4 Correct 1 ms 776 KB Output is correct
5 Correct 2 ms 776 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Runtime error 1 ms 344 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 684 KB Output is correct
2 Correct 321 ms 684 KB Output is correct
3 Correct 605 ms 684 KB Output is correct
4 Correct 483 ms 684 KB Output is correct
5 Correct 416 ms 684 KB Output is correct
6 Correct 289 ms 684 KB Output is correct
7 Correct 269 ms 684 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 310 ms 684 KB Output is correct
12 Correct 374 ms 688 KB Output is correct
13 Correct 602 ms 684 KB Output is correct
14 Correct 410 ms 684 KB Output is correct
15 Correct 408 ms 684 KB Output is correct
16 Correct 287 ms 684 KB Output is correct
17 Runtime error 1 ms 344 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -