oj.uz

답안 #1063109

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063109 2024-08-17T14:18:24 Z nightfal 기지국 (IOI20_stations) C++17
44.0422 / 100
 648 ms 1020 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, vector<vector<int>> &g, vector<int> &pre, vector<int> &post) {
	if (pre[node]!=-1) return cnt;
	pre[node] = cnt++;
	for(int child: g[node])
		cnt = dfs2(child,cnt,g,pre,post);
	post[node] = cnt++;
	return cnt;
}
void label5(int n, vector<vector<int>> &g, vector<int> &labels) {
	vector<int> pre(n,-1), post(n,-1);
	dfs2(0,0,g,pre,post);
	for(int i=0; i<n; i++)
		labels[i] = pre[i]*2000 + post[i];
	// 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) {
	// if (s >= pow(10,7)) return 4;
	if (s >= 2'000 || t >= 2'000) return 5;
	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 preS = s/2000, postS = s%2000;
	int preT = t/2000, postT = t%2000;
	int m = c.size();
	// cout << "s:" << s << " t:" << t<< endl;

	if (preT < preS || postS < postT) return c[0];
	else {
		for(int i=1; i<m; i++) 
			if(preT < c[i]/2000) 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:95:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  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:80:25: warning: control reaches end of non-void function [-Wreturn-type]
   80 |  vector<vector<int>> g(n);
      |                         ^
stations.cpp: In function 'int find3(int, int, std::vector<int>&)':
stations.cpp:117:1: warning: control reaches end of non-void function [-Wreturn-type]
  117 | }
      | ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 348 ms 684 KB Output is correct
2 Correct 277 ms 688 KB Output is correct
3 Correct 629 ms 684 KB Output is correct
4 Correct 469 ms 684 KB Output is correct
5 Correct 407 ms 684 KB Output is correct
6 Correct 319 ms 688 KB Output is correct
7 Correct 334 ms 684 KB Output is correct
8 Correct 1 ms 1016 KB Output is correct
9 Correct 1 ms 776 KB Output is correct
10 Correct 0 ms 764 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 327 ms 684 KB Output is correct
2 Correct 366 ms 684 KB Output is correct
3 Correct 588 ms 684 KB Output is correct
4 Correct 438 ms 684 KB Output is correct
5 Correct 374 ms 684 KB Output is correct
6 Correct 270 ms 684 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 684 KB Output is correct
2 Correct 280 ms 684 KB Output is correct
3 Correct 588 ms 684 KB Output is correct
4 Correct 408 ms 684 KB Output is correct
5 Correct 379 ms 684 KB Output is correct
6 Correct 335 ms 684 KB Output is correct
7 Correct 286 ms 684 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 780 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Incorrect 359 ms 688 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 590 ms 684 KB Output is correct
2 Correct 453 ms 684 KB Output is correct
3 Correct 354 ms 684 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 1 ms 772 KB Output is correct
6 Correct 0 ms 764 KB Output is correct
7 Correct 360 ms 684 KB Output is correct
8 Correct 648 ms 684 KB Output is correct
9 Correct 437 ms 684 KB Output is correct
10 Correct 395 ms 684 KB Output is correct
11 Correct 3 ms 764 KB Output is correct
12 Correct 4 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 1 ms 768 KB Output is correct
15 Correct 0 ms 776 KB Output is correct
16 Correct 363 ms 684 KB Output is correct
17 Correct 309 ms 684 KB Output is correct
18 Correct 336 ms 684 KB Output is correct
19 Correct 321 ms 684 KB Output is correct
20 Correct 319 ms 684 KB Output is correct

Subtask #5
21.0422 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 372 ms 684 KB Partially correct
2 Partially correct 318 ms 684 KB Partially correct
3 Partially correct 549 ms 684 KB Partially correct
4 Partially correct 454 ms 684 KB Partially correct
5 Partially correct 438 ms 684 KB Partially correct
6 Partially correct 285 ms 684 KB Partially correct
7 Partially correct 316 ms 684 KB Partially correct
8 Partially correct 2 ms 768 KB Partially correct
9 Partially correct 2 ms 768 KB Partially correct
10 Partially correct 1 ms 764 KB Partially correct
11 Partially correct 248 ms 684 KB Partially correct
12 Partially correct 334 ms 688 KB Partially correct
13 Partially correct 543 ms 936 KB Partially correct
14 Partially correct 469 ms 772 KB Partially correct
15 Partially correct 376 ms 684 KB Partially correct
16 Partially correct 328 ms 704 KB Partially correct
17 Partially correct 392 ms 684 KB Partially correct
18 Partially correct 327 ms 764 KB Partially correct
19 Partially correct 326 ms 764 KB Partially correct
20 Partially correct 311 ms 684 KB Partially correct
21 Partially correct 29 ms 764 KB Partially correct
22 Partially correct 43 ms 768 KB Partially correct
23 Partially correct 52 ms 716 KB Partially correct
24 Partially correct 3 ms 768 KB Partially correct
25 Partially correct 2 ms 764 KB Partially correct
26 Partially correct 3 ms 776 KB Partially correct
27 Partially correct 2 ms 768 KB Partially correct
28 Partially correct 0 ms 776 KB Partially correct
29 Partially correct 320 ms 684 KB Partially correct
30 Partially correct 320 ms 684 KB Partially correct
31 Partially correct 341 ms 684 KB Partially correct
32 Partially correct 359 ms 684 KB Partially correct
33 Partially correct 342 ms 684 KB Partially correct
34 Partially correct 233 ms 888 KB Partially correct
35 Partially correct 321 ms 932 KB Partially correct
36 Partially correct 312 ms 680 KB Partially correct
37 Partially correct 294 ms 684 KB Partially correct
38 Partially correct 341 ms 936 KB Partially correct
39 Partially correct 296 ms 1020 KB Partially correct
40 Partially correct 330 ms 768 KB Partially correct
41 Partially correct 355 ms 1020 KB Partially correct
42 Partially correct 33 ms 760 KB Partially correct
43 Partially correct 63 ms 716 KB Partially correct
44 Partially correct 86 ms 684 KB Partially correct
45 Partially correct 102 ms 948 KB Partially correct
46 Partially correct 209 ms 684 KB Partially correct
47 Partially correct 219 ms 684 KB Partially correct
48 Partially correct 31 ms 764 KB Partially correct
49 Partially correct 45 ms 740 KB Partially correct