Submission #1176977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176977		12345678	Split the Attractions (IOI19_split)	C++17	22 / 100	540 ms	1114112 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int sz[nx], c, h[nx], szc[nx], cnt, sm;
vector<pair<int, int>> d[nx], t;
vector<int> res;
pair<int, int> mx;

int dfssz(int u, int p)
{
    sz[u]=1;
    for (auto [v, idx]:d[u]) if (v!=p) sz[u]+=dfssz(v, u);
    return sz[u];
}

void dfsfill(int u, int p, int hd)
{
    h[u]=hd;
    szc[hd]++;
    for (auto [v, idx]:d[u]) if (v!=p) dfsfill(v, u, hd);
}

void fillans(int u, int p, int ans)
{
    if (cnt==0) return;
    res[u]=ans;
    cnt--;
    if (cnt==0) return;
    for (auto [v, idx]:d[u]) if (v!=p&&!res[v]) fillans(v, u, ans);
}

int findcentroid(int u, int p, int rtsz)
{
    for (auto [v, idx]:d[u]) if (v!=p&&2*sz[v]>rtsz) return findcentroid(v, u, rtsz); 
    return u;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    res.resize(n,0);
    t.push_back({a, 1});
    t.push_back({b, 2});
    t.push_back({c, 3});
    sort(t.begin(), t.end());
    for (int i=0; i<p.size(); i++) d[p[i]].push_back({q[i], i}), d[q[i]].push_back({p[i], i});
    dfssz(0, 0);
    //for (int i=0; i<n; i++) cout<<"sz "<<i<<' '<<sz[i]<<'\n';
    c=findcentroid(0, 0, n);
    for (auto [v, idx]:d[c]) 
    {
        dfsfill(v, c, v);
        sm+=szc[v];
        mx=max(mx, {szc[v], v});
    }
    if (sm!=n-1) cout<<1/0;
    if (mx.first>=t[0].first)
    {
        cnt=t[0].first;
        fillans(mx.second, c, t[0].second);
        if (cnt>0) cout<<1/0;
        cnt=t[1].first;
        fillans(c, mx.second, t[1].second);
        for (int i=0; i<n;i ++) if (!res[i]) res[i]=t[2].second;
        return res;
    }
    return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:58:25: warning: division by zero [-Wdiv-by-zero]
   58 |     if (sm!=n-1) cout<<1/0;
      |                        ~^~
split.cpp:63:27: warning: division by zero [-Wdiv-by-zero]
   63 |         if (cnt>0) cout<<1/0;
      |                          ~^~

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