oj.uz

Submission #1040775

# Submission time Handle Problem Language Result Execution time Memory
1040775 2024-08-01T09:05:54 Z 김은성(#10995) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 217 ms 9980 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include "incursion.h"
using namespace std;
typedef long long ll;
const ll INF = 0x3fffffffffffffff;
int d[45009];
bool ch[45009];
vector<int> graph[45009];
bool mar[6] = {0, 0, 1, 1, 0, 1};
void dfs(int v){
	ch[v] = 1;
	for(int i=0; i<graph[v].size(); i++){
		int u = graph[v][i];
		if(ch[u])
			continue;
		d[u] = d[v] + 1;
		dfs(u);
	}
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
	int n = (int)F.size() + 1, i;
	for(i=0; i<n-1; i++){
		graph[F[i].first].push_back(F[i].second);
		graph[F[i].second].push_back(F[i].first);
	}
	dfs(safe);
	vector<int> ret(n);
	for(i=0; i<n; i++){
		ret[i] = mar[d[i+1] % 6];
		if(graph[i+1].size() == 1){
			if(safe != i+1 && safe != graph[i+1][0])
				ret[i] = 1;
			else
				ret[i] = 0;
		}
	}
	return ret;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
	int n = (int)F.size() + 1, i, j;
	int cor = 0;
	for(i=1; i<=n; i++){
		graph[i].clear();
		ch[i] = 0;
	}
	for(i=0; i<n-1; i++){
		graph[F[i].first].push_back(F[i].second);
		graph[F[i].second].push_back(F[i].first);
	}
	if(graph[curr].size() == 2){
		int c1 = visit(graph[curr][0]);
		int c2 = visit(curr);
		int c3 = visit(graph[curr][1]);
		visit(curr);
		if(c1 + c2 + c3 == 0)
			return;
	vector<int> colors;
	colors.push_back(t);
	vector<int> st;
	st.push_back(curr);
	int v = curr;
	for(i=0; i<10; i++){
		ch[v] = 1;
		for(j=0; j<graph[v].size(); j++){
			if(!ch[graph[v][j]]){
				st.push_back(graph[v][j]);
				colors.push_back(visit(graph[v][j]));
				v= graph[v][j];
				break;
			}
		}
		if(j == graph[v].size()){
			if(colors.back() == 0)
				return;
			else
				break;
		}
	}
	while(1){
		st.pop_back();
		if(st.empty())
			break;
		visit(st.back());
	}
	memset(ch, 0, sizeof(ch));
	if(colors.size() != 11){
		cor = 1;
		for(i=0; i+2<colors.size(); i++){
			if(colors[i] + colors[i+1] + colors[i+2] == 0)
				cor = 0;
		}
	}
	else{
		bool flag = 0;
		for(i=0; i+2<colors.size(); i++){
			if(colors[i] + colors[i+1] + colors[i+2] == 0)
				cor = 0, flag = 1;
		}
		if(flag==0){
		for(i=0; i<11; i++){
			if(colors[i] == 0)
				break;
		}
		for(i++; i<11; i++){
			if(colors[i] == 1)
				break;
		}
		int cnt = 0, cnt2 = 0;
		for(; i<11; i++){
			if(colors[i] == 1)
				cnt++;
			else
				break;
		}
		for(; i<11; i++){
			if(colors[i] == 0)
				cnt2++;
			else
				break;
		}
		//printf("cnt=%d cnt2=%d\n", cnt, cnt2);
		if(cnt2>=3 || cnt == cnt2)
			cor = 0;
		else
			cor = 1;
		}
	}
	}
	memset(ch, 0, sizeof(ch));
	int zero = 1 - t;
	ch[curr] = 1;
	ch[graph[curr][cor]] = 1;
	int v = graph[curr][cor];
	if(visit(v) == 0)
		zero++;
	else
		zero = 0;
	while(1){
		ch[v] = 1;
		//printf("v=%d zero=%d\n", v, zero);
		if(zero == 3 || graph[v].size() == 1){
			//printf("v=%d zero=%d\n", v, zero);
			if(graph[v].size()==1 && zero != 0 && zero != 3)
				return;
			for(int j=0; j<graph[v].size(); j++){
				if(ch[graph[v][j]]){
					visit(graph[v][j]);
					return; 
				}
			}
		}
		for(int i=0; i<graph[v].size(); i++){
			if(ch[graph[v][i]] && i+1 != graph[v].size())
				continue;
			if(visit(graph[v][i]) == 0)
				zero++;
			else
				zero = 0;
			v = graph[v][i];
			break;
		}
	}
}

Compilation message

incursion.cpp: In function 'void dfs(int)':
incursion.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0; i<graph[v].size(); i++){
      |               ~^~~~~~~~~~~~~~~~
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:72:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(j=0; j<graph[v].size(); j++){
      |            ~^~~~~~~~~~~~~~~~
incursion.cpp:80:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   if(j == graph[v].size()){
      |      ~~^~~~~~~~~~~~~~~~~~
incursion.cpp:96:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for(i=0; i+2<colors.size(); i++){
      |            ~~~^~~~~~~~~~~~~~
incursion.cpp:103:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(i=0; i+2<colors.size(); i++){
      |            ~~~^~~~~~~~~~~~~~
incursion.cpp:153:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |    for(int j=0; j<graph[v].size(); j++){
      |                 ~^~~~~~~~~~~~~~~~
incursion.cpp:160:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |   for(int i=0; i<graph[v].size(); i++){
      |                ~^~~~~~~~~~~~~~~~
incursion.cpp:161:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |    if(ch[graph[v][i]] && i+1 != graph[v].size())
      |                          ~~~~^~~~~~~~~~~~~~~~~~
interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2820 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 9560 KB Correct
2 Correct 169 ms 9604 KB Correct
3 Correct 96 ms 9600 KB Correct
4 Correct 84 ms 9076 KB Correct
5 Correct 168 ms 9072 KB Correct
6 Correct 67 ms 8588 KB Correct
7 Correct 65 ms 8512 KB Correct
8 Correct 164 ms 9604 KB Correct
9 Correct 158 ms 9600 KB Correct
10 Correct 132 ms 9064 KB Correct
11 Correct 78 ms 9096 KB Correct
12 Correct 199 ms 9352 KB Correct
13 Correct 73 ms 8556 KB Correct
14 Correct 68 ms 8516 KB Correct
15 Correct 156 ms 9552 KB Correct
16 Correct 184 ms 9608 KB Correct
17 Correct 119 ms 9032 KB Correct
18 Correct 90 ms 9116 KB Correct
19 Correct 124 ms 9064 KB Correct
20 Correct 59 ms 8300 KB Correct
21 Correct 63 ms 8528 KB Correct
22 Correct 193 ms 9620 KB Correct
23 Correct 182 ms 9604 KB Correct
24 Correct 83 ms 8808 KB Correct
25 Correct 79 ms 9604 KB Correct
26 Correct 70 ms 8864 KB Correct
27 Correct 71 ms 8564 KB Correct
28 Correct 69 ms 8576 KB Correct
29 Correct 184 ms 9848 KB Correct
30 Correct 186 ms 9980 KB Correct
31 Correct 67 ms 8356 KB Correct
32 Correct 182 ms 9116 KB Correct
33 Correct 216 ms 9368 KB Correct
34 Correct 63 ms 8560 KB Correct
35 Correct 62 ms 8348 KB Correct
36 Correct 186 ms 9588 KB Correct
37 Correct 197 ms 9540 KB Correct
38 Correct 217 ms 9208 KB Correct
39 Correct 112 ms 9356 KB Correct
40 Correct 158 ms 9360 KB Correct
41 Correct 60 ms 8356 KB Correct
42 Correct 62 ms 8348 KB Correct
43 Correct 183 ms 9856 KB Correct
44 Correct 156 ms 9624 KB Correct
45 Correct 70 ms 9080 KB Correct
46 Correct 63 ms 9328 KB Correct
47 Correct 76 ms 9096 KB Correct
48 Correct 68 ms 8552 KB Correct
49 Correct 63 ms 8348 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 7552 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2820 KB Correct
2 Correct 199 ms 9560 KB Correct
3 Correct 169 ms 9604 KB Correct
4 Correct 96 ms 9600 KB Correct
5 Correct 84 ms 9076 KB Correct
6 Correct 168 ms 9072 KB Correct
7 Correct 67 ms 8588 KB Correct
8 Correct 65 ms 8512 KB Correct
9 Correct 164 ms 9604 KB Correct
10 Correct 158 ms 9600 KB Correct
11 Correct 132 ms 9064 KB Correct
12 Correct 78 ms 9096 KB Correct
13 Correct 199 ms 9352 KB Correct
14 Correct 73 ms 8556 KB Correct
15 Correct 68 ms 8516 KB Correct
16 Correct 156 ms 9552 KB Correct
17 Correct 184 ms 9608 KB Correct
18 Correct 119 ms 9032 KB Correct
19 Correct 90 ms 9116 KB Correct
20 Correct 124 ms 9064 KB Correct
21 Correct 59 ms 8300 KB Correct
22 Correct 63 ms 8528 KB Correct
23 Correct 193 ms 9620 KB Correct
24 Correct 182 ms 9604 KB Correct
25 Correct 83 ms 8808 KB Correct
26 Correct 79 ms 9604 KB Correct
27 Correct 70 ms 8864 KB Correct
28 Correct 71 ms 8564 KB Correct
29 Correct 69 ms 8576 KB Correct
30 Correct 184 ms 9848 KB Correct
31 Correct 186 ms 9980 KB Correct
32 Correct 67 ms 8356 KB Correct
33 Correct 182 ms 9116 KB Correct
34 Correct 216 ms 9368 KB Correct
35 Correct 63 ms 8560 KB Correct
36 Correct 62 ms 8348 KB Correct
37 Correct 186 ms 9588 KB Correct
38 Correct 197 ms 9540 KB Correct
39 Correct 217 ms 9208 KB Correct
40 Correct 112 ms 9356 KB Correct
41 Correct 158 ms 9360 KB Correct
42 Correct 60 ms 8356 KB Correct
43 Correct 62 ms 8348 KB Correct
44 Correct 183 ms 9856 KB Correct
45 Correct 156 ms 9624 KB Correct
46 Correct 70 ms 9080 KB Correct
47 Correct 63 ms 9328 KB Correct
48 Correct 76 ms 9096 KB Correct
49 Correct 68 ms 8552 KB Correct
50 Correct 63 ms 8348 KB Correct
51 Incorrect 65 ms 7552 KB Not correct
52 Halted 0 ms 0 KB -