oj.uz

답안 #1063200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063200 2024-08-17T15:10:38 Z nightfal 기지국 (IOI20_stations) C++17
71 / 100
 641 ms 1196 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 5;
	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 label1(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 label2(int n, vector<int> &labels) {
	for(int i=0; i<n; i++) labels[i] = i+1;
}
void label3(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 label4(vector<vector<int>> &g, vector<int> &labels) {
	labels[0] = pow(10,7);
	dfs(0,pow(10,6),g,labels);
}
int dfs2(int node, int cnt, int d, vector<vector<int>> &g, vector<int> &pre, vector<int> &post, vector<int> &dist) {
	if (pre[node]!=-1) return cnt;
	pre[node] = cnt++;
	dist[node] = d++;
	for(int child: g[node])
		cnt = dfs2(child,cnt,d,g,pre,post,dist);
	post[node] = cnt++;
	return cnt;
}
void relabel(int n, vector<int> &labels) {
	vector<pair<int,int>> temp;
	for(int i=0; i<n; i++)
		temp.push_back({labels[i],i});
	sort(temp.begin(),temp.end());
	for(int i=0; i<n; i++)
		labels[temp[i].second] = i;
}
void label5(int n, vector<vector<int>> &g, vector<int> &labels) {
	vector<int> pre(n,-1), post(n,-1), dist(n,-1);
	dfs2(0,0,0,g,pre,post,dist);
	for(int i=0; i<n; i++)
		labels[i] = dist[i]%2? post[i]:pre[i];
	relabel(n, labels);
	// print(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: label1(n,g,labels); return labels;
		case 2: label2(n,labels); return labels;
		case 3: label3(n,g,labels); return labels;
		case 4: label4(g,labels); return labels;
		case 5: label5(n,g,labels); return labels;
	}
}
int findSubDecision(int s, int t, vector<int> &c) {
	return 5;
	// 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 find1(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 find2(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 find3(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 && s < t) { 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 find4(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 find5(int s, int t, vector<int> &c) {
	int m = c.size();
	// cout << "s:" << s << " t:" << t<< endl;
	if (m==1) return c[0];
	else if (s==0) { for(int elem: c) if(t<=elem) return elem; }
	else if (s<c[0]) { // s is pre and c[i] is post.
		if (t<s) return c[m-1];
		for(int i=0; i<m-1; i++) if (t<=c[i]) return c[i];
		return c[m-1];
	}
	else { // s is post and c[i] is pre.
		if (t>s) return c[0];
		for(int i=1; i<m; i++) 
			if(t < c[i]) return c[i-1];
		return c[m-1];
	}
}
int find_next_station(int s, int t, std::vector<int> c) {
	int subtask = findSubDecision(s,t,c);
	switch(subtask) {
		case 1: return find1(s,t,c);
		case 2: return find2(s,t,c);
		case 3: return find3(s,t,c);
		case 4: return find4(s,t,c);
		case 5: return find5(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 label3(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:106:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  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:90:25: warning: control reaches end of non-void function [-Wreturn-type]
   90 |  vector<vector<int>> g(n);
      |                         ^
stations.cpp: In function 'int find3(int, int, std::vector<int>&)':
stations.cpp:128:1: warning: control reaches end of non-void function [-Wreturn-type]
  128 | }
      | ^
stations.cpp: In function 'int find5(int, int, std::vector<int>&)':
stations.cpp:158:1: warning: control reaches end of non-void function [-Wreturn-type]
  158 | }
      | ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 398 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 295 ms 688 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 382 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 582 ms 688 KB Output is correct
2 Correct 462 ms 684 KB Output is correct
3 Correct 478 ms 684 KB Output is correct
4 Correct 1 ms 772 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 0 ms 760 KB Output is correct
7 Correct 381 ms 684 KB Output is correct
8 Correct 607 ms 684 KB Output is correct
9 Correct 453 ms 684 KB Output is correct
10 Correct 397 ms 684 KB Output is correct
11 Correct 2 ms 764 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Correct 2 ms 776 KB Output is correct
14 Correct 2 ms 776 KB Output is correct
15 Correct 1 ms 772 KB Output is correct
16 Correct 357 ms 772 KB Output is correct
17 Correct 347 ms 684 KB Output is correct
18 Correct 335 ms 684 KB Output is correct
19 Correct 372 ms 684 KB Output is correct
20 Correct 398 ms 684 KB Output is correct

Subtask #5
61.0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 389 ms 940 KB Output is correct
2 Correct 269 ms 940 KB Output is correct
3 Correct 616 ms 684 KB Output is correct
4 Correct 479 ms 684 KB Output is correct
5 Correct 394 ms 684 KB Output is correct
6 Correct 303 ms 940 KB Output is correct
7 Correct 318 ms 684 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 318 ms 776 KB Output is correct
12 Correct 397 ms 684 KB Output is correct
13 Correct 641 ms 684 KB Output is correct
14 Correct 442 ms 684 KB Output is correct
15 Correct 380 ms 684 KB Output is correct
16 Correct 319 ms 688 KB Output is correct
17 Correct 409 ms 684 KB Output is correct
18 Correct 306 ms 1196 KB Output is correct
19 Correct 340 ms 1016 KB Output is correct
20 Correct 306 ms 684 KB Output is correct
21 Correct 25 ms 716 KB Output is correct
22 Correct 37 ms 744 KB Output is correct
23 Correct 55 ms 972 KB Output is correct
24 Correct 2 ms 768 KB Output is correct
25 Correct 3 ms 768 KB Output is correct
26 Correct 3 ms 768 KB Output is correct
27 Correct 1 ms 768 KB Output is correct
28 Correct 0 ms 768 KB Output is correct
29 Correct 342 ms 776 KB Output is correct
30 Correct 375 ms 684 KB Output is correct
31 Correct 386 ms 684 KB Output is correct
32 Correct 333 ms 684 KB Output is correct
33 Correct 329 ms 684 KB Output is correct
34 Correct 218 ms 940 KB Output is correct
35 Correct 297 ms 1036 KB Output is correct
36 Correct 295 ms 1188 KB Output is correct
37 Correct 327 ms 932 KB Output is correct
38 Correct 290 ms 1012 KB Output is correct
39 Correct 289 ms 1024 KB Output is correct
40 Correct 289 ms 768 KB Output is correct
41 Correct 312 ms 932 KB Output is correct
42 Correct 36 ms 768 KB Output is correct
43 Correct 69 ms 768 KB Output is correct
44 Correct 95 ms 736 KB Output is correct
45 Correct 97 ms 1192 KB Output is correct
46 Correct 185 ms 684 KB Output is correct
47 Correct 183 ms 684 KB Output is correct
48 Correct 31 ms 760 KB Output is correct
49 Correct 38 ms 808 KB Output is correct