ACM-ICPC World Finals 2016 F解法 - でも今日はSRMあるから

F: Longest Rivers

問題

n+m+1頂点、葉がn個の重み付き根付き木が与えられる。
各葉は川の源流で、川は辺にそって根の方向に続く。すべての辺はただ一つの川に属する。
(辺をn個の川に分割する、一つの川はつながって枝分かれしない。合流した川はいずれか一つの川の名前を持って根に向かって伸びる。)
どの辺がどの川に属するかはわからない。
長い川のランキングを作るとき、各葉から伸びる川は最良で何位になるか求めよ。
同じ長さに成る時は任意の順番で良い。

制約

n <= 500000
m <= n-1 (節点)

解法

ある川一つについて考えてみる。
その川を最良の順位にするので、最長にするように根まで全てその川にするべきである。
その長さをLとする。
他の川はL以下にしたい、Lより長い川を少なくしたい。
ある頂点について、葉の方から幾つかの川が合流したとき:

Lより長い川がある => その川(最も長い川)を根に向かって伸ばす
全てL以下 => 最も短い川を根に向かって伸ばす

これが最適である。特に2つめは短い川が伸ばした先でLを超えるなら長いのを選んでも短いのを選んでも損得は同じである。
貪欲にできそうであるので木DPで順位を求めることができる。しかしこれはO(N^2)でTLE。

問題はLより長い川を最低いくつ作らなければならないか？である。
葉から伸びた川がLを超えたらそれ以上伸ばす必要はない。
逆にLが増加したら、止まっていた川が再び伸び出す。各葉についてのクエリをオフライン問題(クエリをソート)にすると良い。

Lは各葉からの最長の川の長さを小さい順に取る(木DPで簡単に求まる)。
優先度付きキューには常にLより長い川を入れておく。
L以下になった川は親に吸収されてキューから消える。
子の川が全て合流した頂点は、それらの川は全てL以下なので、最も短いものを親に向かって伸ばす処理をキューに入れる。
こうして(キューのサイズ+1)がその時のLの解となる。

コード

#include<queue>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

const int MAXN = 1000111;
int N, K;
string name[500111];

struct Edge {
    int dst;
    LL cst;
};
vector<Edge> G[MAXN];

int par[MAXN];
LL par_len[MAXN];
LL dist[MAXN];
LL mi[MAXN];
int cnt[MAXN];
int ans[MAXN];

char buf[999];


int main() {
    scanf("%d%d", &N, &K);
    REP (i, N) {
	int p, c;
	scanf("%s%d%d", buf, &p, &c);
	name[i] = buf;
	p += N;
	G[p].push_back((Edge){ i, c });
	G[i].push_back((Edge){ p, c });
	par[i] = p;
    }
    REP (i, K) {
	int p, c, v = i + N + 1;
	scanf("%d%d", &p, &c);
	p += N;
	G[p].push_back((Edge){ v, c });
	G[v].push_back((Edge){ p, c });
	par[v] = p;
    }

    par[N] = -1;
    VI ord; ord.reserve(N + K + 1);
    ord.push_back(N);
    REP (i, N+K+1) {
	int v = ord[i];
	EACH (e, G[v]) if (e->dst != par[v]) {
	    cnt[v]++;
	    dist[e->dst] = dist[v] + e->cst;
	    par_len[e->dst] = e->cst;
	    ord.push_back(e->dst);
	}
    }
    cnt[N] = -1;

    vector<pair<LL, int> > query(N);
    priority_queue<pair<LL, int>, vector<pair<LL, int> >, greater<pair<LL, int> > > Q;

    REP (i, N) {
	query[i] = make_pair(dist[i], i);
	Q.push(make_pair(par_len[i], i));
    }
    sort(query.begin(), query.end());

    memset(mi, 0x3f, sizeof mi);

    EACH ($, query) {
	LL L = $->first;
	int I = $->second;

	while (!Q.empty() && Q.top().first <= L) {
	    pair<LL, int> x = Q.top(); Q.pop();
	    int v = x.second; LL c = x.first;

	    amin(mi[par[v]], c);
	    cnt[par[v]]--;
	    if (cnt[par[v]] == 0) {
		Q.push(make_pair(mi[par[v]] + par_len[par[v]], par[v]));
	    }
	}

	ans[I] = Q.size();
    }
    
    REP (i, N) {
	printf("%s %d\n", name[i].c_str(), ans[i] + 1);
    }

    return 0;
}

日記

唯一のアルゴリズミックな問題。感動。SRMっぽい。