oj.uz

Submission #1072052

# Submission time Handle Problem Language Result Execution time Memory
1072052 2024-08-23T13:43:08 Z amin The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 276 ms 79444 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=1;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 12 ms 51144 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 78536 KB Correct
2 Correct 221 ms 78200 KB Correct
3 Correct 123 ms 68784 KB Correct
4 Correct 102 ms 70296 KB Correct
5 Correct 209 ms 75492 KB Correct
6 Correct 92 ms 70920 KB Correct
7 Correct 83 ms 74776 KB Correct
8 Correct 247 ms 76272 KB Correct
9 Correct 214 ms 78276 KB Correct
10 Correct 169 ms 76264 KB Correct
11 Correct 101 ms 67212 KB Correct
12 Correct 266 ms 79444 KB Correct
13 Correct 79 ms 67620 KB Correct
14 Correct 89 ms 70820 KB Correct
15 Correct 228 ms 78408 KB Correct
16 Correct 210 ms 78520 KB Correct
17 Correct 124 ms 76416 KB Correct
18 Correct 91 ms 77204 KB Correct
19 Correct 181 ms 75420 KB Correct
20 Correct 90 ms 74776 KB Correct
21 Correct 87 ms 74852 KB Correct
22 Correct 222 ms 72500 KB Correct
23 Correct 224 ms 78492 KB Correct
24 Correct 100 ms 72472 KB Correct
25 Correct 103 ms 77972 KB Correct
26 Correct 100 ms 72592 KB Correct
27 Correct 81 ms 63120 KB Correct
28 Correct 82 ms 68888 KB Correct
29 Correct 193 ms 78508 KB Correct
30 Correct 232 ms 69816 KB Correct
31 Correct 101 ms 75636 KB Correct
32 Correct 257 ms 69556 KB Correct
33 Correct 276 ms 72508 KB Correct
34 Correct 98 ms 66976 KB Correct
35 Correct 87 ms 63476 KB Correct
36 Correct 245 ms 69048 KB Correct
37 Correct 232 ms 69100 KB Correct
38 Correct 273 ms 68784 KB Correct
39 Correct 154 ms 77380 KB Correct
40 Correct 200 ms 64900 KB Correct
41 Correct 80 ms 68996 KB Correct
42 Correct 96 ms 69004 KB Correct
43 Correct 219 ms 70868 KB Correct
44 Correct 247 ms 70440 KB Correct
45 Correct 93 ms 72612 KB Correct
46 Correct 94 ms 73244 KB Correct
47 Correct 115 ms 70560 KB Correct
48 Correct 93 ms 69004 KB Correct
49 Correct 95 ms 70952 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 67228 KB Correct
2 Incorrect 88 ms 65356 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 51144 KB Correct
2 Correct 247 ms 78536 KB Correct
3 Correct 221 ms 78200 KB Correct
4 Correct 123 ms 68784 KB Correct
5 Correct 102 ms 70296 KB Correct
6 Correct 209 ms 75492 KB Correct
7 Correct 92 ms 70920 KB Correct
8 Correct 83 ms 74776 KB Correct
9 Correct 247 ms 76272 KB Correct
10 Correct 214 ms 78276 KB Correct
11 Correct 169 ms 76264 KB Correct
12 Correct 101 ms 67212 KB Correct
13 Correct 266 ms 79444 KB Correct
14 Correct 79 ms 67620 KB Correct
15 Correct 89 ms 70820 KB Correct
16 Correct 228 ms 78408 KB Correct
17 Correct 210 ms 78520 KB Correct
18 Correct 124 ms 76416 KB Correct
19 Correct 91 ms 77204 KB Correct
20 Correct 181 ms 75420 KB Correct
21 Correct 90 ms 74776 KB Correct
22 Correct 87 ms 74852 KB Correct
23 Correct 222 ms 72500 KB Correct
24 Correct 224 ms 78492 KB Correct
25 Correct 100 ms 72472 KB Correct
26 Correct 103 ms 77972 KB Correct
27 Correct 100 ms 72592 KB Correct
28 Correct 81 ms 63120 KB Correct
29 Correct 82 ms 68888 KB Correct
30 Correct 193 ms 78508 KB Correct
31 Correct 232 ms 69816 KB Correct
32 Correct 101 ms 75636 KB Correct
33 Correct 257 ms 69556 KB Correct
34 Correct 276 ms 72508 KB Correct
35 Correct 98 ms 66976 KB Correct
36 Correct 87 ms 63476 KB Correct
37 Correct 245 ms 69048 KB Correct
38 Correct 232 ms 69100 KB Correct
39 Correct 273 ms 68784 KB Correct
40 Correct 154 ms 77380 KB Correct
41 Correct 200 ms 64900 KB Correct
42 Correct 80 ms 68996 KB Correct
43 Correct 96 ms 69004 KB Correct
44 Correct 219 ms 70868 KB Correct
45 Correct 247 ms 70440 KB Correct
46 Correct 93 ms 72612 KB Correct
47 Correct 94 ms 73244 KB Correct
48 Correct 115 ms 70560 KB Correct
49 Correct 93 ms 69004 KB Correct
50 Correct 95 ms 70952 KB Correct
51 Correct 92 ms 67228 KB Correct
52 Incorrect 88 ms 65356 KB Not correct
53 Halted 0 ms 0 KB -