oj.uz

Submission #1072247

# Submission time Handle Problem Language Result Execution time Memory
1072247 2024-08-23T15:57:21 Z Abito The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 212 ms 14988 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);
	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{
				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;
					}
				}
				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;
					}
				}
				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:131:13: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
  131 |    if (d[b[j]]){
      |             ^
incursion.cpp:82:13: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |    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 3 ms 5384 KB Correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 14620 KB Correct
2 Correct 212 ms 14988 KB Correct
3 Correct 111 ms 14856 KB Correct
4 Incorrect 97 ms 14684 KB Not correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

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

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5384 KB Correct
2 Correct 201 ms 14620 KB Correct
3 Correct 212 ms 14988 KB Correct
4 Correct 111 ms 14856 KB Correct
5 Incorrect 97 ms 14684 KB Not correct
6 Halted 0 ms 0 KB -