oj.uz

답안 #1062586

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1062586 2024-08-17T08:53:40 Z nightfal 기지국 (IOI20_stations) C++17
29 / 100
 587 ms 872 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) {
	if(labels[node]!=-1) return;
	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:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0; i<g[node].size(); i++)
      |               ~^~~~~~~~~~~~~~~
stations.cpp: In function 'int findSubDecision(int, int, std::vector<int>&)':
stations.cpp:87:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  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:72:25: warning: control reaches end of non-void function [-Wreturn-type]
   72 |  vector<vector<int>> g(n);
      |                         ^
stations.cpp: In function 'int findSub3(int, int, std::vector<int>&)':
stations.cpp:124:1: warning: control reaches end of non-void function [-Wreturn-type]
  124 | }
      | ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 375 ms 684 KB Output is correct
2 Correct 328 ms 684 KB Output is correct
3 Correct 587 ms 684 KB Output is correct
4 Correct 455 ms 684 KB Output is correct
5 Correct 363 ms 684 KB Output is correct
6 Correct 256 ms 684 KB Output is correct
7 Correct 239 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 1 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 684 KB Output is correct
2 Correct 291 ms 684 KB Output is correct
3 Correct 560 ms 772 KB Output is correct
4 Correct 425 ms 688 KB Output is correct
5 Correct 392 ms 684 KB Output is correct
6 Correct 314 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 684 KB Output is correct
2 Correct 278 ms 792 KB Output is correct
3 Correct 485 ms 768 KB Output is correct
4 Correct 363 ms 776 KB Output is correct
5 Correct 287 ms 768 KB Output is correct
6 Correct 257 ms 684 KB Output is correct
7 Correct 256 ms 684 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 351 ms 768 KB Output is correct
12 Correct 267 ms 872 KB Output is correct
13 Correct 313 ms 764 KB Output is correct
14 Correct 282 ms 684 KB Output is correct
15 Correct 27 ms 768 KB Output is correct
16 Correct 49 ms 744 KB Output is correct
17 Correct 62 ms 684 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 553 ms 688 KB Output is correct
2 Correct 452 ms 684 KB Output is correct
3 Correct 402 ms 684 KB Output is correct
4 Correct 1 ms 764 KB Output is correct
5 Incorrect 3 ms 764 KB Wrong query response.
6 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 588 KB Invalid labels (duplicates values). scenario=1, label=12244897
2 Halted 0 ms 0 KB -