oj.uz

답안 #1062401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1062401 2024-08-17T06:06:29 Z nightfal 기지국 (IOI20_stations) C++17
13 / 100
 644 ms 944 KB 
#include <vector>
#include <iostream>
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) {
	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, int k, 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,i,g,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);
	// 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,k,g,labels); return labels;
	}
}
int findSubDecision(int s, int t, vector<int> &c) {
	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;
	}
}
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);
	}
	return c[0];
}

Compilation message

stations.cpp: In function 'void makeG(std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
stations.cpp:10:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  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:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0; i<u.size(); i++)
      |               ~^~~~~~~~~
stations.cpp:23:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   23 |   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, 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[root].size(); i++)
      |               ~^~~~~~~~~~~~~~~
stations.cpp: In function 'int findSubDecision(int, int, std::vector<int>&)':
stations.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  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:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:58:25: warning: control reaches end of non-void function [-Wreturn-type]
   58 |  vector<vector<int>> g(n);
      |                         ^
stations.cpp: In function 'int findSub3(int, int, std::vector<int>&)':
stations.cpp:108:1: warning: control reaches end of non-void function [-Wreturn-type]
  108 | }
      | ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 363 ms 684 KB Output is correct
2 Correct 283 ms 684 KB Output is correct
3 Correct 577 ms 684 KB Output is correct
4 Correct 454 ms 944 KB Output is correct
5 Correct 373 ms 684 KB Output is correct
6 Correct 321 ms 684 KB Output is correct
7 Correct 292 ms 684 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 684 KB Output is correct
2 Correct 376 ms 684 KB Output is correct
3 Correct 617 ms 684 KB Output is correct
4 Correct 487 ms 684 KB Output is correct
5 Correct 384 ms 684 KB Output is correct
6 Correct 326 ms 684 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 324 ms 684 KB Output is correct
2 Correct 309 ms 688 KB Output is correct
3 Correct 582 ms 684 KB Output is correct
4 Correct 450 ms 684 KB Output is correct
5 Correct 390 ms 684 KB Output is correct
6 Correct 288 ms 684 KB Output is correct
7 Correct 296 ms 684 KB Output is correct
8 Correct 1 ms 776 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 764 KB Output is correct
11 Incorrect 1 ms 344 KB Invalid labels (values out of range). scenario=1, k=1000000, vertex=3, label=-1
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 644 ms 684 KB Output is correct
2 Correct 482 ms 680 KB Output is correct
3 Correct 404 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Incorrect 0 ms 344 KB Invalid labels (values out of range). scenario=0, k=1000000000, vertex=3, label=-1
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 378 ms 684 KB Output is correct
2 Correct 351 ms 684 KB Output is correct
3 Correct 635 ms 684 KB Output is correct
4 Correct 432 ms 712 KB Output is correct
5 Correct 444 ms 684 KB Output is correct
6 Correct 345 ms 684 KB Output is correct
7 Correct 297 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 772 KB Output is correct
11 Correct 286 ms 684 KB Output is correct
12 Correct 340 ms 684 KB Output is correct
13 Correct 633 ms 684 KB Output is correct
14 Correct 484 ms 684 KB Output is correct
15 Correct 418 ms 684 KB Output is correct
16 Correct 309 ms 684 KB Output is correct
17 Incorrect 1 ms 344 KB Invalid labels (values out of range). scenario=0, k=1000000000, vertex=3, label=-1
18 Halted 0 ms 0 KB -