Submission #1369413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1369413		zhivko	Split the Attractions (IOI19_split)	C++20	0 / 100	529 ms	1114112 KiB

split

#include<bits/stdc++.h>
#include "split.h"
using namespace std;
int n,a,b;
int m;
vector<int>v[100001];
bool used[100001];
int sz[100001];
void dfs_fein(int node,int p)
{
    sz[node]=1;
    for(int& i:v[node])
    {
        if(i==p||used[i])continue;
        dfs_fein(i,node);
        sz[node]+=sz[i];
    }
}
int h=0;
bool cmp(int a,int b)
{
    return sz[a]>sz[b];
}
int find_cent(int node)
{
    for(int& i:v[node])
    {
        if(used[i])continue;
        if(sz[i]>=h)return find_cent(i);
        else return node;
    }
    return node;
}
void decomp(int node)
{
    dfs_fein(node,-1);
    h=(sz[node]+1)/2;
    int c=find_cent(node);
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q)
{
    n=N;
    a=A;
    b=B;
	m=p.size();
	for(int i=0;i<m;i++)
    {
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
    }
    decomp(1);
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:52:1: warning: no return statement in function returning non-void [-Wreturn-type]
   52 | }
      | ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36