[KOI 2010 본선] 체인점

문제 링크

이 문제를 풀기 전에 BOI의 굉장한 학생을 먼저 풀어보시는 것을 추천드립니다.

풀이

다익스트라로 $A$로부터의 거리, $B$로부터의 거리, $C$로부터의 거리를 구한 뒤,

$A$로부터의 거리의 오름차순으로 $B$로부터의 거리를 좌표압축한 인덱스에 $C$로부터의 거리를 업데이트해주면 된다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
void o_o(){ cerr << endl; }
template <class H, class...T> void o_o(H h,T...t) { cerr << ' ' << h; o_o(t...); }
#define debug(...) cerr<<'['<<#__VA_ARGS__<<"]:",o_o(__VA_ARGS__)
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define size(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 1e5+3;
bool possible[N];
vector<pair<int,ll>> adj[N];

struct segment_tree {
    ll t[2*N];
    segment_tree() { fill(t,t+2*N,1e18); }
    void update(int k, ll v) {
        k += N, mup(t[k], v);
        while ((k /= 2) >= 1) {
            t[k] = min(t[2*k], t[2*k+1]);
        }
    }
    ll query(int a, int b) {
        ll r = t[0];
        for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
            if (a&1) mup(r,t[a]);
            if (~b&1) mup(r,t[b]);
        }
        return r;
    }
} ds;

void dijkstra(int x, ll dist[]) {
    priority_queue<pair<ll,int>> pq;
    pq.emplace(0,x), dist[x] = 0;
    while (not empty(pq)) {
        auto [d,a] = pq.top(); d=-d, pq.pop();
        if (d != dist[a]) continue;
        for (auto [b,w] : adj[a]) {
            if (dist[b] > d+w) {
                dist[b] = d+w;
                pq.emplace(-d-w,b);
            }
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, a, b, c, m, t;
    cin >> n >> a >> b >> c >> m;
    rep(i,1,m) {
        int x, y, z;
        cin >> x >> y >> z;
        adj[x].emplace_back(y,z);
        adj[y].emplace_back(x,z);
    }
    
    vector<int> v(n);
    vector<ll> bs;
    ll da[N], db[N], dc[N];
    rep(i,1,n) da[i] = db[i] = dc[i] = 1e18;
    dijkstra(a,da), dijkstra(b,db), dijkstra(c,dc);
    
    // rep(i,1,n) debug(i,da[i],db[i],dc[i]);
    
    rep(i,1,n) bs.push_back(db[i]);
    sort(all(bs)), bs.erase(unique(all(bs)),end(bs));
    rep(i,1,n) db[i] = lower_bound(all(bs),db[i])-begin(bs);
    
    iota(all(v),1);
    sort(all(v),[&](int &x, int &y) { return da[x] < da[y]; });
    for (int i = 0, j; i < size(v);) {
        for (j = i; j < size(v) and da[v[i]] == da[v[j]]; ++j) {
            possible[v[j]] = ds.query(0,db[v[j]]-1) >= dc[v[j]];
        }
        for (; i < j; ++i)
            ds.update(db[v[i]],dc[v[i]]);
    }
    cin >> t; rep(_,1,t)
    {
        int q; cin >> q;
        if (possible[q]) {
            cout << "YES\n";
        } else cout << "NO\n";
    }
}

디버깅

94%에서 WA를 받았다. 이미 oikorea.org에서 100점을 맞았기에, 데추주가 있었나본데... 어딜까?

싶어서 고민해보니 $A$로부터의 거리가 같은 경우 strictly 작은 경우가 아닌 등호가 들어간 작은 경우까지 고려되기 때문에,

$A$로부터의 거리가 같은 경우는 한번에 처리해주었다.

 

그런데도 틀리길래 뭔가 싶었는데 $A$로부터의 거리를 정렬한 인덱스를 들고 오는게 아니라 그냥 인덱스를 들고 써버렸다.

그니까 [ v[i] ]가 되어야 하는데 [ i ]를 쓴 것이다. 그런데도 oikorea.org에서는 100점이 나왔어서 미친건가 싶었다.

oikorea.org 데이터 ㄹㅇ 너무 약하다 ㅋㅋ