Submission #603242

#	Time	Username	Problem	Language	Result	Execution time	Memory
603242		MatijaL	Race (IOI11_race)	C++14	21 / 100	1218 ms	57456 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define loop(i, a) FOR(i, 0, a-1)
typedef long long ll;
#define pll pair<ll, ll>
const int maxn=400000;
map<int, char> ans;
set<int> adj[maxn];
map<pll, ll> cost;
#define fs first
#define sc second

const bool DEBUG=0;

ll dist[maxn];
ll depth[maxn];
int sz[maxn];

ll K;
ll best=1e9;

int dfs(int u, int p){
    sz[u]=1;
    for(auto e:adj[u]){
        if(e==p)continue;
        sz[u]+=dfs(e, u);
    }
    return sz[u];
}
set<pll> pre;
vector<pll> cur;
void dfs2(int u, int p, ll d){
    dist[u]=d;
    depth[u]=depth[p]+1;
    if(d==K) best=min(best, depth[u]);
    cur.pb(mp(d, depth[u]));
    for(auto e:adj[u]){
        if(e==p) continue;
        dfs2(e, u, d+cost[mp(u, e)]);
    }
}

int centroid(int u, int p, int N){
    for(auto e : adj[u]){
        if(e==p)continue;
        if(sz[e]*2 > N) return centroid(e, u, N);
    }
    return u;
}
void decompose(char let, int v){
    dfs(v, v);
    int c = centroid(v, v, sz[v]);
    ans[c]=let;
    if(sz[v]==1) return;

    //Prestej poti
    vector<int> rem(adj[c].begin(), adj[c].end());
    pre.clear();
    if(DEBUG) printf("Decomposing on %d\n", c);
    for(auto e : rem){
        depth[c]=0;
        dfs2(e, c, cost[mp(c, e)]);
        if(DEBUG)printf("child %d\n", e);
        for(auto p : cur){
            if(DEBUG)printf("path %d %d\n", p.fs, p.sc);
            auto b = *pre.lower_bound(mp(K-p.fs, 0));
            if(b.fs+p.fs==K) best=min(best, p.sc+b.sc);
        }

        for(auto _e : cur)pre.insert(_e);
        cur.clear();
    }

    //Rekurzivno razstavi
    for(auto e : rem){
        adj[c].erase(e);adj[e].erase(c);
        decompose(let+1, e);
    }
}

int best_path(int N, int _K, int H[][2], int L[]){
  FOR(i, 0, N-2){
    int a=H[i][0], b=H[i][1];
    adj[a].insert(b);adj[b].insert(a);
    cost[mp(a,b)]=L[i];cost[mp(b, a)]=L[i];
  }
  K=_K;
  decompose(0, 0);
  if(best==1e9)return -1;
  return best;
}

Compilation message (stderr)

race.cpp: In function 'void decompose(char, int)':
race.cpp:69:36: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   69 |             if(DEBUG)printf("path %d %d\n", p.fs, p.sc);
      |                                   ~^
      |                                    |
      |                                    int
      |                                   %lld
race.cpp:69:39: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   69 |             if(DEBUG)printf("path %d %d\n", p.fs, p.sc);
      |                                      ~^
      |                                       |
      |                                       int
      |                                      %lld

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57