oj.uz

Submission #1072045

# Submission time Handle Problem Language Result Execution time Memory
1072045 2024-08-23T13:40:04 Z amin The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 285 ms 78556 KB 
#include <vector>
#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
int sz[1000000];
int p[1000000];
int vis[1000000];
vector<int>v[1000000];
int n;
int centroid;
int ans[1000000];
void fin(int in,int col)
{
	vis[in]=1;
	vector<pair<int,int> >k;
	if(p[in]!=in)
	k.push_back({n-sz[in],p[in]});
	//cout<<in<<'  '<<k.size()<<endl;
	for(auto i:v[in])
	{
		if(i==p[in])
		continue;
		k.push_back({sz[i],i});
	}
	sort(k.begin(),k.end());
	int o=k.size()-1;
	if(col==1)
	{
	for(auto i:k)
	{
		if(i.first==k[o].first&&vis[i.second]==0)
		{
			int newcol=visit(i.second);
			fin(i.second,newcol);
			return ;
		}
	}
	int newcol=visit(k[o].second);
	fin(k[o].second,newcol);
	return ;
    }
    if(k.size()==1)
    return ;
    for(auto i:k)
	{
		//cout<<in<<' '<<i.firsti.second<<' '<<k.size()<<endl;
		if(i.first==k[0].first&&vis[i.second]==0)
		{
			int newcol=visit(i.second);
			fin(i.second,newcol);
			return ;
		}
		
	}
    


}

void dfs(int in,int par)
{
	sz[in]=1;
	p[in]=par;
for(auto i:v[in])
{
	if(i==par)
	continue;
	dfs(i,in);
	sz[in]+=sz[i];
}
if(in==par)
{
	ans[in]=0;
	//return ;
}else
{
int h=1;
int j=n-sz[in];
for(auto i:v[in])
{
	if(i==par)
	continue;
	if(sz[i]>j)
	h=0;
}

ans[in]=h;
//cout<<in<<' '<<ans[in]<<endl;
}
}
vector<int> mark(vector<pair<int, int>> f, int safe) {
	n=f.size()+1;
 vector<int>u;
 for(int i=0;i<n-1;i++)
 {
	 v[f[i].first].push_back(f[i].second);
	 v[f[i].second].push_back(f[i].first);
 }
 dfs(safe,safe);
 
 for(int i=1;i<=n;i++)
 {
	 u.push_back(ans[i]);
 }
 return u;
}

void locate(vector<pair<int, int>> f, int curr, int t) {
  n=f.size()+1;
  for(int i=0;i<n;i++)
  {
	  v[i].clear();
  }
  for(int i=0;i<n-1;i++)
  {
	  v[f[i].first].push_back(f[i].second);
	  v[f[i].second].push_back(f[i].first);
  }
  dfs(curr,curr);
  fin(curr,t);
  return ;
  
}

Compilation message

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 9 ms 62212 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 72468 KB Correct
2 Correct 230 ms 78480 KB Correct
3 Correct 125 ms 66968 KB Correct
4 Correct 93 ms 76456 KB Correct
5 Correct 210 ms 77684 KB Correct
6 Correct 92 ms 65960 KB Correct
7 Correct 91 ms 74912 KB Correct
8 Correct 232 ms 78556 KB Correct
9 Correct 262 ms 69420 KB Correct
10 Correct 159 ms 76536 KB Correct
11 Correct 108 ms 75140 KB Correct
12 Correct 280 ms 71144 KB Correct
13 Correct 84 ms 74752 KB Correct
14 Correct 96 ms 74892 KB Correct
15 Correct 218 ms 78108 KB Correct
16 Correct 201 ms 78428 KB Correct
17 Correct 136 ms 74380 KB Correct
18 Correct 105 ms 75428 KB Correct
19 Correct 174 ms 77280 KB Correct
20 Correct 84 ms 72728 KB Correct
21 Correct 98 ms 74888 KB Correct
22 Correct 230 ms 78428 KB Correct
23 Correct 221 ms 76264 KB Correct
24 Correct 107 ms 77132 KB Correct
25 Correct 98 ms 77952 KB Correct
26 Correct 91 ms 72748 KB Correct
27 Correct 86 ms 65196 KB Correct
28 Correct 93 ms 70996 KB Correct
29 Correct 202 ms 65784 KB Correct
30 Correct 216 ms 72800 KB Correct
31 Correct 98 ms 69524 KB Correct
32 Correct 285 ms 74388 KB Correct
33 Correct 268 ms 78380 KB Correct
34 Correct 87 ms 74788 KB Correct
35 Correct 92 ms 67520 KB Correct
36 Correct 219 ms 64012 KB Correct
37 Correct 240 ms 64336 KB Correct
38 Correct 250 ms 64260 KB Correct
39 Correct 153 ms 75292 KB Correct
40 Correct 202 ms 77440 KB Correct
41 Correct 82 ms 68988 KB Correct
42 Correct 94 ms 69104 KB Correct
43 Correct 262 ms 68712 KB Correct
44 Correct 216 ms 78376 KB Correct
45 Correct 104 ms 76748 KB Correct
46 Correct 99 ms 69516 KB Correct
47 Correct 115 ms 69060 KB Correct
48 Correct 91 ms 74772 KB Correct
49 Correct 91 ms 70940 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 56772 KB Correct
2 Incorrect 88 ms 71320 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 62212 KB Correct
2 Correct 212 ms 72468 KB Correct
3 Correct 230 ms 78480 KB Correct
4 Correct 125 ms 66968 KB Correct
5 Correct 93 ms 76456 KB Correct
6 Correct 210 ms 77684 KB Correct
7 Correct 92 ms 65960 KB Correct
8 Correct 91 ms 74912 KB Correct
9 Correct 232 ms 78556 KB Correct
10 Correct 262 ms 69420 KB Correct
11 Correct 159 ms 76536 KB Correct
12 Correct 108 ms 75140 KB Correct
13 Correct 280 ms 71144 KB Correct
14 Correct 84 ms 74752 KB Correct
15 Correct 96 ms 74892 KB Correct
16 Correct 218 ms 78108 KB Correct
17 Correct 201 ms 78428 KB Correct
18 Correct 136 ms 74380 KB Correct
19 Correct 105 ms 75428 KB Correct
20 Correct 174 ms 77280 KB Correct
21 Correct 84 ms 72728 KB Correct
22 Correct 98 ms 74888 KB Correct
23 Correct 230 ms 78428 KB Correct
24 Correct 221 ms 76264 KB Correct
25 Correct 107 ms 77132 KB Correct
26 Correct 98 ms 77952 KB Correct
27 Correct 91 ms 72748 KB Correct
28 Correct 86 ms 65196 KB Correct
29 Correct 93 ms 70996 KB Correct
30 Correct 202 ms 65784 KB Correct
31 Correct 216 ms 72800 KB Correct
32 Correct 98 ms 69524 KB Correct
33 Correct 285 ms 74388 KB Correct
34 Correct 268 ms 78380 KB Correct
35 Correct 87 ms 74788 KB Correct
36 Correct 92 ms 67520 KB Correct
37 Correct 219 ms 64012 KB Correct
38 Correct 240 ms 64336 KB Correct
39 Correct 250 ms 64260 KB Correct
40 Correct 153 ms 75292 KB Correct
41 Correct 202 ms 77440 KB Correct
42 Correct 82 ms 68988 KB Correct
43 Correct 94 ms 69104 KB Correct
44 Correct 262 ms 68712 KB Correct
45 Correct 216 ms 78376 KB Correct
46 Correct 104 ms 76748 KB Correct
47 Correct 99 ms 69516 KB Correct
48 Correct 115 ms 69060 KB Correct
49 Correct 91 ms 74772 KB Correct
50 Correct 91 ms 70940 KB Correct
51 Correct 95 ms 56772 KB Correct
52 Incorrect 88 ms 71320 KB Not correct
53 Halted 0 ms 0 KB -