답안 #1063214

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1063214	2024-08-17T15:20:26 Z	nightfal	기지국 (IOI20_stations)	C++17	100 / 100	634 ms	1204 KB

stations

#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) {
	return 5;
	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);
}
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();
	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:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0; i<u.size(); i++)
      |               ~^~~~~~~~~
stations.cpp:26:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   26 |   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:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  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: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[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 '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:157:1: warning: control reaches end of non-void function [-Wreturn-type]
  157 | }
      | ^

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	357 ms	940 KB	Output is correct
2	Correct	297 ms	940 KB	Output is correct
3	Correct	611 ms	684 KB	Output is correct
4	Correct	456 ms	688 KB	Output is correct
5	Correct	353 ms	684 KB	Output is correct
6	Correct	312 ms	940 KB	Output is correct
7	Correct	303 ms	940 KB	Output is correct
8	Correct	1 ms	776 KB	Output is correct
9	Correct	2 ms	768 KB	Output is correct
10	Correct	0 ms	776 KB	Output is correct

Subtask #2

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	300 ms	684 KB	Output is correct
2	Correct	368 ms	684 KB	Output is correct
3	Correct	583 ms	684 KB	Output is correct
4	Correct	421 ms	684 KB	Output is correct
5	Correct	413 ms	684 KB	Output is correct
6	Correct	304 ms	684 KB	Output is correct

Subtask #3

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	399 ms	940 KB	Output is correct
2	Correct	299 ms	940 KB	Output is correct
3	Correct	634 ms	684 KB	Output is correct
4	Correct	438 ms	684 KB	Output is correct
5	Correct	435 ms	684 KB	Output is correct
6	Correct	285 ms	940 KB	Output is correct
7	Correct	281 ms	944 KB	Output is correct
8	Correct	1 ms	768 KB	Output is correct
9	Correct	1 ms	768 KB	Output is correct
10	Correct	1 ms	760 KB	Output is correct
11	Correct	412 ms	776 KB	Output is correct
12	Correct	291 ms	1192 KB	Output is correct
13	Correct	301 ms	1204 KB	Output is correct
14	Correct	289 ms	684 KB	Output is correct
15	Correct	25 ms	764 KB	Output is correct
16	Correct	30 ms	776 KB	Output is correct
17	Correct	71 ms	716 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	622 ms	684 KB	Output is correct
2	Correct	471 ms	684 KB	Output is correct
3	Correct	400 ms	684 KB	Output is correct
4	Correct	1 ms	764 KB	Output is correct
5	Correct	1 ms	768 KB	Output is correct
6	Correct	0 ms	768 KB	Output is correct
7	Correct	412 ms	772 KB	Output is correct
8	Correct	615 ms	684 KB	Output is correct
9	Correct	462 ms	684 KB	Output is correct
10	Correct	321 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	768 KB	Output is correct
14	Correct	2 ms	768 KB	Output is correct
15	Correct	0 ms	768 KB	Output is correct
16	Correct	288 ms	684 KB	Output is correct
17	Correct	290 ms	684 KB	Output is correct
18	Correct	278 ms	684 KB	Output is correct
19	Correct	291 ms	684 KB	Output is correct
20	Correct	289 ms	772 KB	Output is correct

Subtask #5

61.0 / 61.0

#	결과	실행 시간	메모리	Grader output
1	Correct	322 ms	940 KB	Output is correct
2	Correct	273 ms	940 KB	Output is correct
3	Correct	527 ms	684 KB	Output is correct
4	Correct	445 ms	684 KB	Output is correct
5	Correct	422 ms	684 KB	Output is correct
6	Correct	304 ms	940 KB	Output is correct
7	Correct	321 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	0 ms	768 KB	Output is correct
11	Correct	301 ms	684 KB	Output is correct
12	Correct	387 ms	684 KB	Output is correct
13	Correct	616 ms	940 KB	Output is correct
14	Correct	486 ms	684 KB	Output is correct
15	Correct	390 ms	684 KB	Output is correct
16	Correct	321 ms	684 KB	Output is correct
17	Correct	387 ms	684 KB	Output is correct
18	Correct	292 ms	1020 KB	Output is correct
19	Correct	333 ms	1012 KB	Output is correct
20	Correct	317 ms	684 KB	Output is correct
21	Correct	40 ms	768 KB	Output is correct
22	Correct	48 ms	688 KB	Output is correct
23	Correct	56 ms	684 KB	Output is correct
24	Correct	2 ms	776 KB	Output is correct
25	Correct	2 ms	768 KB	Output is correct
26	Correct	2 ms	764 KB	Output is correct
27	Correct	2 ms	776 KB	Output is correct
28	Correct	0 ms	776 KB	Output is correct
29	Correct	316 ms	684 KB	Output is correct
30	Correct	352 ms	684 KB	Output is correct
31	Correct	367 ms	684 KB	Output is correct
32	Correct	345 ms	684 KB	Output is correct
33	Correct	350 ms	684 KB	Output is correct
34	Correct	198 ms	940 KB	Output is correct
35	Correct	286 ms	1192 KB	Output is correct
36	Correct	275 ms	940 KB	Output is correct
37	Correct	298 ms	684 KB	Output is correct
38	Correct	314 ms	768 KB	Output is correct
39	Correct	290 ms	772 KB	Output is correct
40	Correct	274 ms	768 KB	Output is correct
41	Correct	297 ms	932 KB	Output is correct
42	Correct	42 ms	764 KB	Output is correct
43	Correct	58 ms	772 KB	Output is correct
44	Correct	76 ms	744 KB	Output is correct
45	Correct	90 ms	716 KB	Output is correct
46	Correct	196 ms	684 KB	Output is correct
47	Correct	210 ms	684 KB	Output is correct
48	Correct	33 ms	848 KB	Output is correct
49	Correct	40 ms	768 KB	Output is correct