제출 #465845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465845		jli12345	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	7 ms	5836 KiB

bitaro

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

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

const int SQRT = 316;

vector<int> arr[100100];

vector<pair<int, int> > far[100100];

int dist[100100];
int vis[100100];

bool cmp(int a, int b){
    return dist[a] > dist[b];
}

int main(){
    fastIO();
    int N, M, Q;
    cin >> N >> M >> Q;
    for (int i = 1; i <= M; i++){
        int a, b; cin >> a >> b;
        arr[b].push_back(a);
    }
    for (int i = 1; i <= N; i++){
        vector<int> all;
        all.push_back(i);
        dist[i] = 0;
        for (int j = 0; j < (int)arr[i].size(); j++){
            int nx = arr[i][j];
            for (int k = 0; k < (int)far[nx].size(); k++){
                if (vis[far[nx][k].second] != i){
                    dist[far[nx][k].second] = far[nx][k].first+1;
                    all.push_back(far[nx][k].second);
                    vis[far[nx][k].second] = i;
                } else {
                    dist[far[nx][k].second] = max(dist[far[nx][k].second], far[nx][k].first+1);
                }
            }
        }
        sort(all.begin(), all.end(), cmp);
        for (int j = 0; j < min((int)all.size(), SQRT); j++){
            far[i].push_back({dist[all[j]], all[j]});
        }
        sort(far[i].begin(), far[i].end(), greater<pair<int, int> >());
    }
    /*
    for (int i = N; i >= 1; i--){
        cout << i << ":\n";
        for (pair<int, int> x : far[i])
            cout << x.first << " " << x.second << "\n";
        cout << "\n";
    }*/
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= Q; i++){
        int T, R; cin >> T >> R;
        for (int j = 1; j <= R; j++){
            int y; cin >> y;
            vis[y] = i;
        }
        if (R < SQRT){
            bool work = false;
            for (int j = 0; j < (int)far[T].size(); j++){
                int nx = far[T][j].second;
                if (vis[nx] != i){
                    cout << far[T][j].first << "\n";
                    work = true;
                    break;
                }
            }
            if (!work)
                cout << -1 << "\n";
        } else {
            /*
            memset(dist, -1, sizeof(dist));
            dist[T] = 0;
            for (int j = T; j >= 1; j--){
                for (int nx : arr[j]){
                    dist[nx] = max(dist[nx], dist[j]+1);
                }
            }
            int mx = -1;
            for (int j = T; j >= 1; j--){
                if (vis[j] == i)
                    continue;
                mx = max(mx, dist[j]);
            }
            cout << mx << "\n";*/
            vector<int> dp(N+1, -1);
			for (int j = 1; j <= T; j++){
				if (vis[j] != i){
					dp[j] = max(dp[j], 0);
				}
                for (int k : arr[j]){
					if (dp[j] != -1){
                        dp[j] = max(dp[j], dp[k]+1);
                    }
				}
			}
			cout << dp[T] << '\n';
        }
    }
}

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