Submission #1313741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313741		orzorzorz	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2113 ms	351148 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;

// 根據題目限制 N=10^5, B 取 sqrt(N) 約 320 左右效果最好
const int mxN = 1e5 + 5;
const int B = 320; 

vector<int> adj[mxN];
// best[i] 存儲到達節點 i 的最長路徑候選列表: {距離, 起點}
vector<pair<int, int>> best[mxN]; 

// 大查詢用的 DP 陣列
int dp[mxN];
bool is_busy[mxN]; // 用陣列取代 set 檢查 busy，O(1) 查詢

int main() {
    // 必要的 IO 優化
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, q;
    cin >> n >> m >> q;
    
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
    }

    // --- 預處理 (Precalc) ---
    // 因為題目保證 S < E，直接 0~N 迴圈即為拓撲序
    for(int i = 0; i < n; i++) {
        // 1. 加入自己作為起點 (距離 0)
        best[i].push_back({0, i});
        
        // 2. 排序並去重 (Sort & Unique)
        // 目標：只保留距離最遠的前 B 個「不同起點」
        sort(best[i].rbegin(), best[i].rend());
        
        vector<pair<int, int>> temp;
        // 用一個簡單的迴圈去重，只要湊滿 B 個就停
        // 這裡不需要 set，因為 B 很小，線性掃描 vector 檢查重複很快
        // 或者使用 visited 陣列標記已經加入的 source
        
        // 為了極致效率，這裡用一個臨時的小 vector 檢查重複即可
        // 由於 B 很小，N^2 檢查其實也只有 320*320，且通常遠小於此
        // 更好的方式是用一個 static visited array，但要記得清空
        // 這裡採用簡單掃描法
        
        // 收集前 B 個不重複來源
        // 為了避免每次都掃描 temp，我們可以用一個標記陣列
        // 但要注意每次清空的成本。
        // 簡單寫法：
        int cnt = 0;
        vector<pair<int,int>> unique_best;
        // 這裡可以用一個 static bitset 或 array 來判斷 source 是否出現過
        // 但因為 source id 可能很大，我們用一個簡單的策略：
        // 因為已經按距離大到小排序，遇到的第一個 source X 一定是來自 X 的最長路徑
        
        static int seen[mxN]; // 標記 source 是否已加入
        static int timer = 0; // 用時間戳記來避免 memset
        timer++;
        
        for(auto &p : best[i]) {
            if(cnt >= B) break;
            if(seen[p.second] != timer) {
                seen[p.second] = timer;
                unique_best.push_back(p);
                cnt++;
            }
        }
        best[i] = unique_best; // 更新 best[i] 為剪枝後的結果

        // 3. 傳播給鄰居 (Propagate)
        // 關鍵：這時候 best[i] 只有 B 個元素，所以複製很快
        for(int v : adj[i]) {
            for(auto &p : best[i]) {
                best[v].push_back({p.first + 1, p.second});
            }
        }
    }

    // --- 處理查詢 ---
    while(q--) {
        int t, y;
        cin >> t >> y;
        --t;
        
        vector<int> busy_list(y);
        for(int i = 0; i < y; i++) {
            cin >> busy_list[i];
            --busy_list[i];
        }

        if(y < B) {
            // 小查詢：直接查表
            int ans = -1;
            for(auto &p : best[t]) {
                bool busy = false;
                for(int b : busy_list) {
                    if(b == p.second) {
                        busy = true;
                        break;
                    }
                }
                if(!busy) {
                    ans = p.first;
                    break;
                }
            }
            cout << ans << "\n";
        } else {
            // 大查詢：暴力 DP
            // 標記 busy 節點
            for(int b : busy_list) is_busy[b] = true;
            
            // 初始化 DP
            // 只需要跑到 t 即可，後面的點不影響
            for(int i = 0; i <= t; i++) dp[i] = -1e9;
            
            for(int i = 0; i <= t; i++) {
                if(!is_busy[i]) {
                    dp[i] = max(dp[i], 0); // 自己可以是起點
                }
                
                // 如果此點不可達 (dp[i] < 0)，就不更新鄰居
                if(dp[i] >= 0) {
                    for(int v : adj[i]) {
                        if(v <= t) { // 優化：只更新 t 之前的點
                            dp[v] = max(dp[v], dp[i] + 1);
                        }
                    }
                }
            }
            
            cout << (dp[t] < 0 ? -1 : dp[t]) << "\n";
            
            // 還原 busy 標記 (比 memset 快)
            for(int b : busy_list) is_busy[b] = false;
        }
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86