[JOISC 2018 Day 3] Bitaro's Party ★

문제 링크

• usaco.guide에서 sqrt decomposition 예제로 제일 쉬운거로 추천되어 있었는데, 그걸 왜 곧이곧대로 믿었을까요...
• 풀 때 사진 참고하세요.

맞왜TLE?

문제 번역

\(1\)부터 \(N\)까지 높이에 대한 내림차순으로 번호가 매겨진 \(N\)개의 마을들이 있습니다.(같은 높이의 마을은 없습니다.) \(M\)개의 운하는 서로 다른 마을을 단방향으로 연결합니다. \(i\)번째 운하(\(1\le i\le M\))은 높은 \(S_i\)에서 낮은 \(E_i\)로 흐릅니다. 운하는 거꾸로 거슬러 올라갈 수 없습니다.

비버 Bitaro의 \(N\)명의 친구들은 \(N\)개의 마을에 살고 있습니다.

Bitaro는 \(Q\)번의 파티를 열며, 친구들을 초대할 것입니다. \(j\)번째 파티에는 \(Y_j\)명의 친구들이 바빠서 못 온다는 것이 알려져 있습니다. \(j\)번째 파티는 \(T_j\) 마을에서 열리므로 \(T_j\) 마을에 갈 수 없는 친구들도 참석하지 못합니다. 이 두 경우가 아닌 친구들만 파티에 참석할 수 있습니다.

각각의 친구들은 운하들을 통해 파티가 열리는 마을에 옵니다. 그 경로는 여러가지가 될 수 있습니다. 하지만 Bitaro의 친구들은 운하를 좋아하므로 가장 많은 운하가 있는 길 중에서 하나를 택합니다.

Bitaro는 가장 많은 수의 운하를 사용한 친구가 얼마나 많은 운하를 사용하는지 궁금해합니다. 파티에 열리는 \(N\)개의 마을들과 \(Q\)번의 파티에 대한 바쁜 친구들의 목록을 고려해 가장 많은 수의 운하를 사용하는 친구가 얼마나 많은 운하를 사용하는지 계산하는 프로그램을 작성해 주십시오.

입력

표준 입출력으로 다음 데이터들이 주어집니다.

• 첫번째 줄은 \(N\), \(M\), \(Q\)가 공백으로 나뉘어 주어집니다. 각각 마을의 개수 \(N\)과 운하의 개수 \(M\), 파티의 횟수 \(Q\)를 의미합니다.
• \(i\)번째 줄(\(1\le i\le M\))은 \(M\)개의 줄에 걸쳐 \(S_i\)와 \(M_i\)들이 주어집니다. \(S_i\)에서 \(E_i\)으로 가는 단방향 운하입니다.
• \(j\)번째 줄(\(1\le j\le Q\))은 \(Q\)개의 줄에 걸쳐 각 줄에 \(T_j\), \(Y_j\), \(C_{j,1}\), \(C_{j,2}\), \(\ldots\), \(C_{j,Y_j}\)가 주어집니다. \(T_j\)에서 열리는 \(j\)번째 파티에 \(C_{j,1}\), \(C_{j,2}\), \(\ldots\), \(C_{j,Y_j}\)들이 바빠서 불참한다는 의미입니다.

출력

\(Q\)개의 줄에 걸쳐 출력합니다. \(j\)번째(\(1\le j\le Q\)) 줄에는 가장 많은 운하를 사용한 친구가 사용한 운하의 개수를 출력합니다. 만약 아무도 참석하지 못한다면 그 줄에는 -1을 출력합니다.

제한

• \(1\le N\le 10^5\)
• \(0\le M\le 2\times 10^5\)
• \(1\le Q\le 10^5\)
• \(1\le S_i<E_i\le N\ (1\le i\le M)\)
• \((S_i,E_i)\neq(S_j,E_j)\ (1\le i<j\le M)\)
• \(1\le T_j\le N\ (1\le j\le Q)\)
• \(0\le Y_j\le N\ (1\le j\le Q)\)
• \(1\le C_{j,1}<C_{j,2}<\cdots <C_{j,Y_j}\le N\ (1\le j\le Q)\)
• \(Y_1+Y_2+\cdots +Y_Q\le 10^5\)

Subtask: \(N\le 1\,000,M\le 2\,000,Q=1\) (7점)

걍 섭태2까지 동시에 긁을 수 있다.

Subtask: \(Q=1\) (7점)

$O(n)$만에 DP로 풀 수 있다.

Fulltask: \(N, Q\le 10^5,M\le 2\cdot 10^5\) (86점)

\(Y_1+Y_2+\cdots +Y_Q= y\le 10^5\)임을 이용해 서브 알고리즘 2개로 제곱근 알고리즘을 짠다.

$Y_i<B:$ 각 정점마다 상위 $B$개의 최장경로를 저장해두면, $O(B)$만에 쿼리에 대한 답을 찾을 수 있다.

$Y_i\ge B:$ 최대 $O(y/B)$번 등장한다. $O(n)$만에 DP로 풀 수 있다.

따라서 시간 복잡도는 전처리를 제외하고 $O(qB)+O(yn/B)$이다.

이때 전처리는 $O(mB)$ 또는 $O(mB\log B)$ 정도에 해줄 수 있다.

상수 $B=100$ 정도가 최적인 것 같았다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#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, B = 100;
int n, m, q;
vector<int> rdj[N];
int dp[N], c[N];
bool come[N];
vector<ii> distances[N];

#define D first
#define F second

void precalc() {
    bool used[N] {0,};
    rep(i,1,n) {
        for (int j : rdj[i]) {
            auto &x = distances[i], &y = distances[j];
            vector<ii> tmp; // tmp <- x + y
            int a = 0, b = 0;
            while (a < size(x) or b < size(y)) {
                if (a >= size(x) or (b < size(y) and y[b].D+1 >= x[a].D)) {
                    if (!used[y[b].F]) tmp.emplace_back(y[b].D+1,y[b].F);
                    used[y[b].F] = true;
                    b++;
                }
                else if (b >= size(y) or (a < size(x) and x[a].D > y[b].D+1)) {
                    if (!used[x[a].F]) tmp.emplace_back(x[a].D,x[a].F);
                    used[x[a].F] = true;
                    a++;
                }
                if (size(tmp) == B) break;
            }
            for (ii t : tmp) used[t.F] = false; // used 복구
            swap(distances[i],tmp); // distances[i] <- tmp
        }
        if (size(distances[i]) < B) distances[i].emplace_back(0,i);
    }
}

int main() {
    scanf("%d%d%d",&n,&m,&q);
    rep(i,1,m) {
        int s, e; scanf("%d%d",&s,&e);
        rdj[e].push_back(s);
    }
    precalc();
    fill(come+1,come+n+1,true);
    rep(_,1,q) {
        int t, y; scanf("%d%d",&t,&y);
        rep(i,1,y) scanf("%d",c+i), come[c[i]] = false;
        if (y >= B) {
            rep(i,1,t) {
                dp[i] = -1e9;
                if (come[i]) Mup(dp[i],0);
                for (const int &j : rdj[i]) {
                    Mup(dp[i],dp[j]+1);
                }
            }
            printf("%d\n",max(dp[t],-1));
        } else {
            int answer = -1e9;
            for (const auto &[dist,from] : distances[t]) {
                if (come[from]) {
                    answer = dist;
                    break;
                }
            }
            printf("%d\n",max(answer,-1));
        }
        rep(i,1,y) come[c[i]] = true;
    }
}