oj.uz

답안 #1062579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1062579 2024-08-17T08:49:12 Z nightfal 기지국 (IOI20_stations) C++17
29 / 100
 1199 ms 2097152 KB 
#include <vector>
#include <iostream>
#include <cmath>
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;
	}
	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);
}
void dfs(int node, int base, int offset, vector<vector<int>> &g, vector<int> &labels) {
	labels[node] = base + offset;
	for(int i=0; i<g[node].size(); i++)
		dfs(g[node][i],labels[node],offset/10*(i+1),g,labels);
	return;
}
void labelSub4(int n, vector<vector<int>> &g, vector<int> &labels) {
	dfs(0,0,pow(10,7),g,labels);
	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 = 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(n,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) {
	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;
	}
}
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) {
	for(int i=c.size()-1; i>=0; i--)
		if(ancestor4(c[i],t)) return c[i];
	return c[0];
}
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:11:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  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: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[root].size(); i++)
      |               ~^~~~~~~~~~~~~~~
stations.cpp: In function 'void dfs(int, int, int, std::vector<std::vector<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<g[node].size(); i++)
      |               ~^~~~~~~~~~~~~~~
stations.cpp: In function 'int findSubDecision(int, int, std::vector<int>&)':
stations.cpp:86:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  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:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:71:25: warning: control reaches end of non-void function [-Wreturn-type]
   71 |  vector<vector<int>> g(n);
      |                         ^
stations.cpp: In function 'int findSub3(int, int, std::vector<int>&)':
stations.cpp:123:1: warning: control reaches end of non-void function [-Wreturn-type]
  123 | }
      | ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 357 ms 688 KB Output is correct
2 Correct 317 ms 712 KB Output is correct
3 Correct 598 ms 684 KB Output is correct
4 Correct 469 ms 684 KB Output is correct
5 Correct 423 ms 684 KB Output is correct
6 Correct 298 ms 940 KB Output is correct
7 Correct 342 ms 684 KB Output is correct
8 Correct 1 ms 776 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 296 ms 684 KB Output is correct
2 Correct 385 ms 684 KB Output is correct
3 Correct 594 ms 684 KB Output is correct
4 Correct 474 ms 684 KB Output is correct
5 Correct 404 ms 684 KB Output is correct
6 Correct 292 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 332 ms 684 KB Output is correct
2 Correct 318 ms 684 KB Output is correct
3 Correct 582 ms 684 KB Output is correct
4 Correct 408 ms 684 KB Output is correct
5 Correct 370 ms 944 KB Output is correct
6 Correct 320 ms 684 KB Output is correct
7 Correct 329 ms 684 KB Output is correct
8 Correct 1 ms 776 KB Output is correct
9 Correct 1 ms 776 KB Output is correct
10 Correct 0 ms 776 KB Output is correct
11 Correct 440 ms 684 KB Output is correct
12 Correct 309 ms 764 KB Output is correct
13 Correct 295 ms 764 KB Output is correct
14 Correct 307 ms 684 KB Output is correct
15 Correct 27 ms 764 KB Output is correct
16 Correct 43 ms 716 KB Output is correct
17 Correct 63 ms 684 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1199 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1076 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -