oj.uz

Submission #1072026

# Submission time Handle Problem Language Result Execution time Memory
1072026 2024-08-23T13:31:10 Z Abito The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 197 ms 17292 KB 
#include <bits/stdc++.h>
#include "incursion.h"
#define pb push_back
using namespace std;
const int N=5e4+5;
int n,par[N],dp[N],a[N],sz[N];
vector<int> adj1[N],adj2[N];
bool vis[N];
void dfs1(int x,int p){
	for (auto u:adj1[x]){
		if (u==p) continue;
		dfs1(u,x);
		dp[x]|=dp[u];
	}return;
}
void dfs2(int x,int p){
	par[x]=p;
	sz[x]=1;
	for (auto u:adj2[x]){
		if (u==p) continue;
		dfs2(u,x);
		sz[x]+=sz[u];
	}return;
}
bool cmp(int x,int y){
	return sz[x]>sz[y];
}
void dfs3(int x,int p){
	if (!a[x]){
		a[par[x]]=visit(par[x]);
		dfs3(par[x],x);
		return;
	}
	for (auto u:adj2[x]){
		if (u==par[x] || u==p) continue;
		a[u]=visit(u);
		if (a[u]==0) visit(x);
		else{
			dfs3(u,x);
			break;
		}
	}
	return;
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
	n=F.size()+1;
	for (auto u:F){
		adj1[u.first].pb(u.second);
		adj1[u.second].pb(u.first);
	}
	dp[safe]=1;
	int r;
	for (int i=1;i<=n;i++) if (adj1[i].size()==2) r=i;
	dfs1(r,0);
	vector<int> v;
	for (int i=1;i<=n;i++) v.pb(dp[i]);
	return v;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
	n=F.size()+1;
	a[curr]=t;
	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()==2) r=i;
	dfs2(r,0);
	for (int i=1;i<=n;i++) sort(adj2[i].begin(),adj2[i].end(),cmp);
	dfs3(curr,0);
	return;
}

Compilation message

incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:54:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |  dfs1(r,0);
      |  ~~~~^~~~~
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:68:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |  dfs2(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 5376 KB Correct

Subtask #1
0.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 10608 KB Correct
2 Correct 101 ms 10880 KB Correct
3 Correct 82 ms 10912 KB Correct
4 Correct 100 ms 14360 KB Correct
5 Correct 119 ms 14360 KB Correct
6 Correct 163 ms 14320 KB Correct
7 Correct 88 ms 10500 KB Correct
8 Correct 84 ms 10480 KB Correct
9 Correct 89 ms 10588 KB Correct
10 Correct 78 ms 10548 KB Correct
11 Correct 76 ms 10524 KB Correct
12 Correct 70 ms 10504 KB Correct
13 Correct 79 ms 10396 KB Correct
14 Correct 53 ms 9276 KB Correct
15 Correct 55 ms 9256 KB Correct
16 Correct 79 ms 10500 KB Correct
17 Correct 79 ms 10552 KB Correct
18 Correct 75 ms 10664 KB Correct
19 Correct 79 ms 10512 KB Correct
20 Correct 61 ms 9288 KB Correct
21 Correct 59 ms 9120 KB Correct
22 Correct 55 ms 9192 KB Correct
23 Correct 65 ms 9264 KB Correct
24 Correct 54 ms 9016 KB Correct
25 Correct 56 ms 9116 KB Correct
26 Correct 78 ms 10532 KB Correct
27 Correct 78 ms 10608 KB Correct
28 Correct 86 ms 10508 KB Correct
29 Correct 89 ms 10412 KB Correct
30 Correct 83 ms 11216 KB Correct
31 Correct 91 ms 10644 KB Correct
32 Correct 96 ms 10812 KB Correct
33 Correct 106 ms 10588 KB Correct
34 Correct 79 ms 10656 KB Correct
35 Correct 84 ms 10680 KB Correct
36 Correct 79 ms 10636 KB Correct
37 Correct 96 ms 10608 KB Correct
38 Correct 89 ms 10508 KB Correct
39 Correct 76 ms 10620 KB Correct
40 Correct 98 ms 10812 KB Correct
41 Correct 91 ms 10676 KB Correct
42 Correct 93 ms 10604 KB Correct
43 Correct 78 ms 10708 KB Correct
44 Correct 79 ms 10640 KB Correct
45 Correct 76 ms 10508 KB Correct
46 Correct 88 ms 10648 KB Correct
47 Correct 83 ms 10908 KB Correct
48 Correct 78 ms 10652 KB Correct
49 Correct 89 ms 10628 KB Correct
50 Correct 92 ms 10516 KB Correct
51 Correct 76 ms 10436 KB Correct
52 Correct 91 ms 10652 KB Correct
53 Correct 82 ms 10604 KB Correct
54 Correct 81 ms 10656 KB Correct
55 Correct 97 ms 10560 KB Correct
56 Correct 76 ms 10644 KB Correct
57 Correct 86 ms 10624 KB Correct
58 Correct 73 ms 10616 KB Correct
59 Correct 78 ms 10620 KB Correct
60 Correct 90 ms 10628 KB Correct
61 Correct 96 ms 10636 KB Correct
62 Correct 73 ms 10632 KB Correct
63 Correct 87 ms 10624 KB Correct
64 Correct 75 ms 10636 KB Correct
65 Correct 73 ms 10628 KB Correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5376 KB Correct
2 Incorrect 197 ms 17292 KB Not correct
3 Halted 0 ms 0 KB -