oj.uz

Submission #1072190

# Submission time Handle Problem Language Result Execution time Memory
1072190 2024-08-23T15:23:49 Z Abito The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 216 ms 14932 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;
	}
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
	n=F.size()+1;
	if (n==2){
		if (t==0) return;
		visit(2);
		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;
					}
				}
				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;
				return;
			}
		}
	}
	return;
}

Compilation message

incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:69:13: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |    if (d[b[j]]){
      |             ^
incursion.cpp:63:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |  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 1 ms 5380 KB Correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 14932 KB Not correct
2 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 1 ms 5380 KB Correct
2 Incorrect 216 ms 14932 KB Not correct
3 Halted 0 ms 0 KB -