Submission #465853

#	Time	Username	Problem	Language	Result	Execution time	Memory
465853		jli12345	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2097 ms	244836 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;
        vis[i] = i;
        for (int j = 0; j < (int)arr[i].size(); j++){
            int nx = arr[i][j];
            if (vis[nx] != i){
                all.push_back(nx);
                dist[nx] = 1;
                vis[nx] = i;
            }
            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]});
        }
    }
    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";
        }*/
        if (R >= SQRT){
            
			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 = 0; k < (int)arr[j].size(); k ++){
					if (dp[arr[j][k]] != -1) dp[j] = max(dp[j], dp[arr[j][k]] + 1);
				}
			}
			cout << dp[T] << '\n';
		} else{
			/*for (int j = 0; j < (int)far[T].size(); j ++){
				if (vis[far[T][j].second] != i){
					cout << far[T][j].first << '\n';
					goto done;
				}
			}
			cout << -1 << '\n';
			done: continue;*/
            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";
		}
    }
}

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