oj.uz

Submission #1072283

# Submission time Handle Problem Language Result Execution time Memory
1072283 2024-08-23T16:21:04 Z Abito The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 251 ms 15096 KB 
#include <bits/stdc++.h>
#include "incursion.h"
#define pb push_back
#define elif else if
using namespace std;
const int N=5e4+5;
int n;
vector<int> adj1[N],a,b,adj2[N];
bool c[N],d[N];
void geta(int x,int p){
	a.pb(x);
	for (auto u:adj1[x]){
		if (u==p) continue;
		geta(u,x);
	}return;
}
void getb(int x,int p){
	b.pb(x);
	for (auto u:adj2[x]){
		if (u==p) continue;
		getb(u,x);
	}return;
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
	n=F.size()+1;
	if (n==2){
		if (safe==1) return {0,1};
		return {1,0};
	}
	for (auto u:F){
		adj1[u.first].pb(u.second);
		adj1[u.second].pb(u.first);
	}
	int r;
	for (int i=1;i<=n;i++) if (adj1[i].size()==1) r=i;
	a.pb(0);
	geta(r,0);
	for (int i=1;i<=n;i++) c[i]=1;
	if (n&1){
		int j;
		for (int i=1;i<=n;i++) if (a[i]==safe) j=i;
		if (j<=n/2+1) for (int i=j;i<=n/2+1;i++) c[a[i]]=0;
		else for (int i=n/2+1;i<=j;i++) c[a[i]]=0;
		vector<int> v;
		for (int i=1;i<=n;i++) v.pb(c[i]);
		return v;
	}
	else{
		int j;
		for (int i=1;i<=n;i++) if (a[i]==safe) j=i;
		if (j==n/2 || j==n/2+1){
			c[safe]=0;	
		}
		elif (j<n/2) for (int i=j;i<=n/2+1;i++) c[a[i]]=0;
		else for (int i=n/2;i<=j;i++) c[a[i]]=0;
		vector<int> v;
		for (int i=1;i<=n;i++) v.pb(c[i]);
		return v;
	}
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
	n=F.size()+1;
	if (n==2){
		if (t==0) return;
		if (curr==1) visit(2);
		else visit(1);
		return;
	}
	for (auto u:F){
		adj2[u.first].pb(u.second);
		adj2[u.second].pb(u.first);
	}
   int r;
	for (int i=1;i<=n;i++) if (adj2[i].size()==1) r=i;
	b.pb(0);
	getb(r,0);
	//for (auto u:b) cout<<u<<' ';
	//cout<<endl;
	if (n&1){
		int j;
		for (int i=1;i<=n;i++) if (b[i]==curr) j=i;
		d[curr]=t;
		while (true){
			if (d[b[j]]){
				if (j<n/2+1){
					j++;
					d[b[j]]=visit(b[j]);
				}
				else{
					j--;
					d[b[j]]=visit(b[j]);
				}
			}
			else{
				//return;
				if (j==1 || j==n) return;
				if (j<n/2+1){
					j--;
					d[b[j]]=visit(b[j]);
					if (d[b[j]]){
						j++;
						visit(b[j]);
						return;
					}
					continue;
				}
				elif (j>n/2+1){
					j++;
					d[b[j]]=visit(b[j]);
					if (d[b[j]]){
						j--;
						visit(b[j]);
						return;
					}
					continue;
				}
				j--;
				d[b[j]]=visit(b[j]);
				if (!d[b[j]]) continue;
				j++;
				d[b[j]]=visit(b[j]);
				j++;
				d[b[j]]=visit(b[j]);
				if (!d[b[j]]) continue;
				j--;d[b[j]]=visit(b[j]);
				return;
			}
		}
	}
	else{
		int j;
		for (int i=1;i<=n;i++) if (b[i]==curr) j=i;
		d[curr]=t;
		while (true){
			if (d[b[j]]){
				if (j<=n/2){
					j++;
					d[b[j]]=visit(b[j]);
				}
				else{
					j--;
					d[b[j]]=visit(b[j]);
				}
			}
			else{
				if (j==1 || j==n) return;
				if (j<n/2){
					j--;
					d[b[j]]=visit(b[j]);
					if (d[b[j]]){
						j++;
						visit(b[j]);
						return;
					}
					continue;
				}
				if (j>n/2+1){
					j++;
					d[b[j]]=visit(b[j]);
					if (d[b[j]]){
						j--;
						visit(b[j]);
						return;
					}
					continue;
				}
				if (j==n/2){
					j--;
					d[b[j]]=visit(b[j]);
					j++;
					d[b[j]]=visit(b[j]);
					j++;
					d[b[j]]=visit(b[j]);
					j++;
					d[b[j]]=visit(b[j]);
					if (d[b[n/2+1]]){
						j--;
						d[b[j]]=visit(b[j]);
						j--;
						d[b[j]]=visit(b[j]);
						return;
					}
					if (!d[b[n/2+2]]) continue;
					j--;
					d[b[j]]=visit(b[j]);
					j--;
					d[b[j]]=visit(b[j]);
					j--;
					d[b[j]]=visit(b[j]);
					continue;
				}
				else{
					j++;
					d[b[j]]=visit(b[j]);
					j--;
					d[b[j]]=visit(b[j]);
					j--;
					d[b[j]]=visit(b[j]);
					j--;
					d[b[j]]=visit(b[j]);
					if (d[b[n/2]]){
						j++;
						d[b[j]]=visit(b[j]);
						j++;
						d[b[j]]=visit(b[j]);
						return;
					}
					if (!d[b[n/2-1]]) continue;
					j++;
					d[b[j]]=visit(b[j]);
					j++;
					d[b[j]]=visit(b[j]);
					j++;
					d[b[j]]=visit(b[j]);
					continue;
				}
			}
		}
		return;
	}
}

Compilation message

incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:135:13: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |    if (d[b[j]]){
      |             ^
incursion.cpp:84:13: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |    if (d[b[j]]){
      |             ^
incursion.cpp:76:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |  getb(r,0);
      |  ~~~~^~~~~
incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:43:26: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |   else for (int i=n/2+1;i<=j;i++) c[a[i]]=0;
      |                         ~^~~
incursion.cpp:37:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |  geta(r,0);
      |  ~~~~^~~~~
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 2 ms 5420 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 15000 KB Correct
2 Correct 192 ms 14856 KB Correct
3 Correct 119 ms 14860 KB Correct
4 Correct 112 ms 14848 KB Correct
5 Correct 192 ms 14852 KB Correct
6 Correct 96 ms 14608 KB Correct
7 Correct 93 ms 14804 KB Correct
8 Correct 241 ms 14856 KB Correct
9 Correct 200 ms 14964 KB Correct
10 Correct 148 ms 14844 KB Correct
11 Correct 112 ms 14844 KB Correct
12 Correct 251 ms 14976 KB Correct
13 Correct 97 ms 14604 KB Correct
14 Correct 82 ms 14708 KB Correct
15 Correct 194 ms 14956 KB Correct
16 Correct 192 ms 14856 KB Correct
17 Correct 121 ms 14844 KB Correct
18 Correct 88 ms 14860 KB Correct
19 Correct 141 ms 14976 KB Correct
20 Correct 91 ms 14588 KB Correct
21 Correct 96 ms 14596 KB Correct
22 Correct 194 ms 14836 KB Correct
23 Correct 218 ms 14860 KB Correct
24 Correct 113 ms 14968 KB Correct
25 Correct 84 ms 14724 KB Correct
26 Correct 99 ms 14608 KB Correct
27 Correct 90 ms 14704 KB Correct
28 Correct 94 ms 14716 KB Correct
29 Correct 217 ms 14964 KB Correct
30 Correct 213 ms 14848 KB Correct
31 Correct 105 ms 14716 KB Correct
32 Correct 228 ms 14852 KB Correct
33 Correct 207 ms 14844 KB Correct
34 Correct 76 ms 14712 KB Correct
35 Correct 86 ms 14704 KB Correct
36 Correct 225 ms 14852 KB Correct
37 Correct 191 ms 14852 KB Correct
38 Correct 248 ms 14952 KB Correct
39 Correct 143 ms 14968 KB Correct
40 Correct 183 ms 14844 KB Correct
41 Correct 82 ms 14608 KB Correct
42 Correct 72 ms 14604 KB Correct
43 Correct 217 ms 14604 KB Correct
44 Correct 202 ms 14964 KB Correct
45 Correct 93 ms 14608 KB Correct
46 Correct 90 ms 14856 KB Correct
47 Correct 104 ms 15096 KB Correct
48 Correct 84 ms 14668 KB Correct
49 Correct 93 ms 14868 KB Correct

Subtask #2
0.0 / 30.0

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

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5420 KB Correct
2 Correct 221 ms 15000 KB Correct
3 Correct 192 ms 14856 KB Correct
4 Correct 119 ms 14860 KB Correct
5 Correct 112 ms 14848 KB Correct
6 Correct 192 ms 14852 KB Correct
7 Correct 96 ms 14608 KB Correct
8 Correct 93 ms 14804 KB Correct
9 Correct 241 ms 14856 KB Correct
10 Correct 200 ms 14964 KB Correct
11 Correct 148 ms 14844 KB Correct
12 Correct 112 ms 14844 KB Correct
13 Correct 251 ms 14976 KB Correct
14 Correct 97 ms 14604 KB Correct
15 Correct 82 ms 14708 KB Correct
16 Correct 194 ms 14956 KB Correct
17 Correct 192 ms 14856 KB Correct
18 Correct 121 ms 14844 KB Correct
19 Correct 88 ms 14860 KB Correct
20 Correct 141 ms 14976 KB Correct
21 Correct 91 ms 14588 KB Correct
22 Correct 96 ms 14596 KB Correct
23 Correct 194 ms 14836 KB Correct
24 Correct 218 ms 14860 KB Correct
25 Correct 113 ms 14968 KB Correct
26 Correct 84 ms 14724 KB Correct
27 Correct 99 ms 14608 KB Correct
28 Correct 90 ms 14704 KB Correct
29 Correct 94 ms 14716 KB Correct
30 Correct 217 ms 14964 KB Correct
31 Correct 213 ms 14848 KB Correct
32 Correct 105 ms 14716 KB Correct
33 Correct 228 ms 14852 KB Correct
34 Correct 207 ms 14844 KB Correct
35 Correct 76 ms 14712 KB Correct
36 Correct 86 ms 14704 KB Correct
37 Correct 225 ms 14852 KB Correct
38 Correct 191 ms 14852 KB Correct
39 Correct 248 ms 14952 KB Correct
40 Correct 143 ms 14968 KB Correct
41 Correct 183 ms 14844 KB Correct
42 Correct 82 ms 14608 KB Correct
43 Correct 72 ms 14604 KB Correct
44 Correct 217 ms 14604 KB Correct
45 Correct 202 ms 14964 KB Correct
46 Correct 93 ms 14608 KB Correct
47 Correct 90 ms 14856 KB Correct
48 Correct 104 ms 15096 KB Correct
49 Correct 84 ms 14668 KB Correct
50 Correct 93 ms 14868 KB Correct
51 Incorrect 83 ms 10504 KB Not correct
52 Halted 0 ms 0 KB -