Submission #43975

#	Time	Username	Problem	Language	Result	Execution time	Memory
43975		wzy	Bitaro’s Party (JOI18_bitaro)	C++11	14 / 100	2041 ms	418856 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
vector<pii> ans[100005];
vector<int> adj[100005];
const int bucket = 350;
int dg[100005];
bool sq[100005];
int dp[100005];
int n , m , qq , target;
int read(){
	char c;
	int a = 0;
	while(!(c>='0' && c<='9'))c = getchar();
	while( c>='0' && c <= '9') a = 10*a + (c - '0') , c = getchar();
	return a;
}


int solve(int i){
	if(i == target) return dp[i] = 0;
	if(dp[i] != -10000000 ) return dp[i];
	for(auto p : adj[i]){
		dp[i] = max(dp[i] , solve(p) + 1);
	}
	return dp[i];
}


int main(){
	n = read() , m = read() , qq = read();
	for(int i = 0 ; i < n; i ++ ) ans[i].pb(pii(0 , i)) , dg[i] = 0;
	for(int i = 0 ; i < m ; i++){
		int x = read() , y = read();
		adj[x-1].pb(y-1);
		dg[y-1]++;
	}
	queue<int> q;
	for(int i = 0 ; i < n; i++) if(dg[i] == 0) q.push(i);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int p : adj[u]){
			dg[p]--;
			vector<pii> a  = ans[u], b = ans[p];
			ans[p].clear();
			int x = 0 , y = 0;
			for(int i = 0 ; i < a.size() + b.size() ; i++){
				if(x == a.size()){
					if(sq[b[y].S] == false)
					ans[p].push_back(pii(b[y].F  , b[y].S)) , sq[b[y].S] = true;
					y++;
				}
				else if(y == b.size()){
					if(sq[a[x].S] == false)
					ans[p].push_back(pii(a[x].F + 1 , a[x].S)) , sq[a[x].S] = true;
					x++;
				}
				else{
					if(a[x].F +1> b[y].F){
						if(sq[a[x].S] == false)
						ans[p].push_back(pii(a[x].F + 1 , a[x].S)) , sq[a[x].S] = true;
						x++;
					}
					else{
						if(sq[b[y].S] == false)
						ans[p].push_back(pii(b[y].F  , b[y].S)) , sq[b[y].S] = true;
						y++;
					}
				}
			}
			a.clear() , b.clear();
			while(ans[p].size() >= bucket)  sq[ans[p].back().S] = 0 , ans[p].pop_back();
			for(int i = 0 ; i < ans[p].size() ; i++) sq[ans[p][i].S] = false;
			if(dg[p] == 0) q.push(p);
		}
	}
	while(qq--){
		int t  = read() , y = read();
		t--;
		vector<int> w(y);
		for(int i = 0 ; i < y ; i ++){
			w[i] = read();
			sq[w[i] - 1] = 1;
		}
		int ansj = -1;
		
		if(y < 337){
			for(int j = 0 ; j < ans[t].size() ; j++){
				if(sq[ans[t][j].S]) continue;
				ansj = max(ansj , ans[t][j].F);
			}
			printf("%d\n" , ansj);
		}	
		else{
			for(int i = 0 ; i < n; i++) dp[i] = -10000000;
			target = t;
			for(int i = 0 ; i <= t ; i++){
				if(sq[i]) continue;
				solve(i);
			}
			for(int i = 0 ; i <= t ;i++){
				if(sq[i]) continue;
				ansj = max(dp[i] , ansj);
			}
			printf("%d\n" , ansj);
		}
		for(int i = 0 ; i < y ; i ++){
			sq[w[i] - 1] = 0;
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0 ; i < a.size() + b.size() ; i++){
                    ~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:52:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(x == a.size()){
        ~~^~~~~~~~~~~
bitaro.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     else if(y == b.size()){
             ~~^~~~~~~~~~~
bitaro.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0 ; i < ans[p].size() ; i++) sq[ans[p][i].S] = false;
                    ~~^~~~~~~~~~~~~~~
bitaro.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < ans[t].size() ; j++){
                    ~~^~~~~~~~~~~~~~~
bitaro.cpp: In function 'int read()':
bitaro.cpp:17:8: warning: 'c' is used uninitialized in this function [-Wuninitialized]
  while(!(c>='0' && c<='9'))c = getchar();
        ^~~~~~~~~~~~~~~~~~~

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