Submission #465850

#	Time	Username	Problem	Language	Result	Execution time	Memory
465850		jli12345	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2109 ms	410988 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;
		for (int j = 0; j < (int)arr[i].size(); j ++){
			int x = arr[i][j];
			for (int k = 0; k < far[x].size(); k ++){
				int z = far[x][k].second;
				if (vis[z] != i){
					vis[z] = i;
					all.push_back(z);
					dist[z] = far[x][k].first + 1;
				} else{
					dist[z] = max(dist[z], far[x][k].first + 1);
				}
			}
			if (vis[x] != i){
				vis[x] = i;
				all.push_back(x);
				dist[x] = 1;
			}
		}
		all.push_back(i);
		sort(all.begin(), all.end(), cmp);
		for (int j = 0; j < min((int)all.size(), SQRT); j ++){
			far[i].push_back(make_pair(dist[all[j]], all[j]));
		}
	}
    /*
    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]});
        }
        sort(far[i].begin(), far[i].end(), greater<pair<int, int> >());
    }*/
    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;
		}
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for (int k = 0; k < far[x].size(); k ++){
      |                    ~~^~~~~~~~~~~~~~~

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