Submission #714107

#	Time	Username	Problem	Language	Result	Execution time	Memory
714107		lam	Towns (IOI15_towns)	C++14	0 / 100	7 ms	796 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
#define ff first
#define ss second
const int maxn = 110;
int n, root, m;
int d[maxn][maxn];
vector <ii> adj[maxn];
int s[maxn],id[maxn],nhanh,rt[maxn];
int dp[maxn];
ii par[maxn];
bool cmp(ii x, ii y)
{
    return s[x.ff]>s[y.ff];
}
void dfs(int x, int p)
{
    s[x] = 1;
    for (ii i:adj[x])
    {
        dfs(i.ff,x);
        par[i.ff]  ={x,i.ss};
        s[x] += s[i.ff];
    }
    rt[x] = x;
    sort(adj[x].begin(),adj[x].end(),cmp);
    if (!adj[x].empty()) rt[x] = rt[adj[x][0].ff];
}
void build(bool nguoc = 0)
{
    for (int i=0; i<m; i++) adj[i].clear(), rt[i] = -1, s[i] = 0;
    for (int i=0; i<m; i++)
    {
        ii u = par[i];
        if (u.ff==i||u.ff==-1) continue;
        adj[u.ff].push_back({i,u.ss});
        if (nguoc) adj[i].push_back({u.ff,u.ss});
    }
    if (!nguoc) dfs(root,root);
}
int Ask(int u, int v)
{
    if (u>v) swap(u,v);
    if (d[u][v] == -1) d[u][v] = getDistance(u,v);
    return d[u][v];
}
void addNode(int p, int w)
{
    par[m++] = {p,w};
}
iii get(int a, int b, int c)
{
    /**
        d = lca(b,c);
    **/
    int ad = (Ask(a,b) + Ask(a,c) - Ask(b,c) ) /2;
    int bd = Ask(a,b) - ad;
    int cd = Ask(a,c) - ad;
//    cerr<<a<<' '<<b<<' '<<c<<" ?? "<<ad<<' '<<bd<<' '<<cd<<endl;
    return {ad,{bd,cd}};
}

void dfs2(int x, int p)
{
    s[x] = (x<n);
    dp[x] = 0;
    for (ii i:adj[x])
        if (i.ff!=p)
    {
        dfs2(i.ff,x);
        s[x] += s[i.ff];
        dp[x] = max(dp[x],dp[i.ff]+i.ss);
    }
}

int hubDistance(int N, int sub) {
    vector <int> a;
    n=N; m=n;
    for (int i=0; i<n; i++) a.push_back(i);
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++) d[i][j] = -1;
//    random_shuffle(a.begin(),a.end());
    for (int i=0; i<n; i++) par[i] = {-1,-1};
    root = a[0];
    iii temp = get(a[0],a[1],a[2]);
    addNode(root,temp.ff);
    par[1] = {m-1,temp.ss.ff};
    par[2] = {m-1,temp.ss.ss};

//        for (int j=0; j<m; j++) cerr<<par[j].ff<<','<<par[j].ss<<' '; cerr<<endl;
    for (int i=3; i<n; i++)
    {
        build();

        int x = root;
        int dist_temp = 0;
        while (true)
        {
            bool check = 1;
            for (ii j:adj[x])
            {
                int v = j.ff;
                iii temp = get(root,rt[v],a[i]);
                if (temp.ff == dist_temp) continue;
                int u = rt[v];
                int dist = 0;
                while (u!=x&&dist + par[u].ss <= temp.ss.ff)
                {
                    dist+=par[u].ss;
                    u=par[u].ff;
                }
//                cerr<<x<<' '<<rt[v]<<' '<<a[i]<<" = "<<u<<' '<<par[u].ff<<','<<par[u].ss<<" : "<<temp.ss.ff<<' '<<dist<<endl;
                if (dist == temp.ss.ff)
                {
                    x=u; check = 0;
                    dist_temp = temp.ff;
                    par[a[i]] = {x,temp.ss.ss};
                    break;
                }
                else
                {
                    addNode(par[u].ff,dist + par[u].ss - temp.ss.ff);
                    par[u] = {m-1, temp.ss.ff - dist};
                    x=u;
                    par[a[i]] = {m-1,temp.ss.ss};
                    check=1;
                    break;
                }
            }
            if (check) break;
        }
//        for (int j=0; j<m; j++) cerr<<par[j].ff<<','<<par[j].ss<<' '; cerr<<endl;
    }
    build(1);
//    for (int i=0; i<m; i++)
//    {
//        cerr<<i<<" := ";
//        for (ii j:adj[i]) cerr<<j.ff<<','<<j.ss<<"  "; cerr<<endl;
//    }
    int R = 1e9;
    int it = -1;
    for (int i=n; i<m; i++)
    {
        dfs2(i,i);
        bool ccheck = 1;
        for (ii j:adj[i]) if (s[j.ff] > n/2) ccheck = 0;
//        cerr<<dp[i]<<" :: "<<ccheck<<endl;
        if (dp[i] < R)
        {
            R = dp[i];
            it = ccheck;
        }
        else if (dp[i] == R) it |=ccheck;
    }
    if (!it) R = -R;
    return R;
}

Compilation message (stderr)

towns.cpp: In function 'void dfs(int, int)':
towns.cpp:19:21: warning: unused parameter 'p' [-Wunused-parameter]
   19 | void dfs(int x, int p)
      |                 ~~~~^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:106:21: warning: declaration of 'temp' shadows a previous local [-Wshadow]
  106 |                 iii temp = get(root,rt[v],a[i]);
      |                     ^~~~
towns.cpp:88:9: note: shadowed declaration is here
   88 |     iii temp = get(a[0],a[1],a[2]);
      |         ^~~~
towns.cpp:79:28: warning: unused parameter 'sub' [-Wunused-parameter]
   79 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39