oj.uz

Submission #73006

# Submission time Handle Problem Language Result Execution time Memory
73006 2018-08-27T13:08:39 Z mraron Bitaro’s Party (JOI18_bitaro) C++14
0 / 100
 31 ms 8352 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> adj[100001];
vector<int> badj[100001];
int indeg[100001];
const int BLKSZ=100;
vector<pair<int,int>> best[100001];
int dp[100010];
int dfs(int x) {
	if(dp[x]!=-2) {
		return dp[x];
	}
	
	int ans=-1;
	for(auto i:badj[x]) {
		ans=max(ans, dfs(i)+1);
	}
	
	return dp[x]=ans;
}
int main() {
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=0;i<m;++i) {
		int a,b;
		cin>>a>>b;
		adj[a].pb(b);
		badj[b].pb(a);
		indeg[b]++;
	}
	
	set<pair<int,int>> st;
	for(int i=1;i<=n;++i) {
		st.insert({indeg[i], i});
	}
	
	while(!st.empty()) {
		pair<int,int> akt=*st.begin();
		//cerr<<akt.first<<" "<<akt.second<<"\n";
		st.erase(st.begin());
		
		priority_queue<pair<int,int>> pq; //(dist, honnan)
		pq.push({0, akt.second});
		for(auto i:badj[akt.second]) {
			for(auto j:best[i]) {
				pq.push({-j.first-1, j.second});
			}
			
			while(pq.size()>BLKSZ) {
				pq.pop();
			}
		}
		
		while(!pq.empty()) {
			best[akt.second].push_back({-pq.top().first, pq.top().second});
			pq.pop();
		}
		
		reverse(best[akt.second].begin(), best[akt.second].end());
		
		for(auto i:adj[akt.second]) {
			auto it=st.lower_bound({indeg[i], i});
			auto val=*it;
			st.erase(it);
			
			val.first--;
			indeg[i]--;
			
			st.insert(val);
		}
	}
	
	for(int i=0;i<q;++i) {
		int place;
		int cnt;
		cin>>place>>cnt;
		vector<int> banned(cnt);
		map<int,int> bannolt;
		
		for(int i=0;i<cnt;++i) {
			cin>>banned[i];
			bannolt[banned[i]]=1;
		}
		
		bool ok=false;
		for(int j=0;j<(int)best[place].size();++j) {
			if(!bannolt[best[place][j].second]) {
				ok=true;
				cout<<best[place][j].first<<"\n";
				break ;
			}
		}
		
		if(ok) {
			continue ;
		}else if(best[place].size()<BLKSZ) {
			cout<<"-1\n";
			continue ;
		}
		
		for(int i=1;i<=place;++i) {
			dp[i]=-2;
		}
		
		cout<<dfs(place)<<"\n";
	}
	
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7288 KB Output is correct
2 Correct 10 ms 7412 KB Output is correct
3 Correct 10 ms 7488 KB Output is correct
4 Correct 8 ms 7612 KB Output is correct
5 Correct 29 ms 8352 KB Output is correct
6 Correct 27 ms 8352 KB Output is correct
7 Incorrect 31 ms 8352 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7288 KB Output is correct
2 Correct 10 ms 7412 KB Output is correct
3 Correct 10 ms 7488 KB Output is correct
4 Correct 8 ms 7612 KB Output is correct
5 Correct 29 ms 8352 KB Output is correct
6 Correct 27 ms 8352 KB Output is correct
7 Incorrect 31 ms 8352 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7288 KB Output is correct
2 Correct 10 ms 7412 KB Output is correct
3 Correct 10 ms 7488 KB Output is correct
4 Correct 8 ms 7612 KB Output is correct
5 Correct 29 ms 8352 KB Output is correct
6 Correct 27 ms 8352 KB Output is correct
7 Incorrect 31 ms 8352 KB Output isn't correct
8 Halted 0 ms 0 KB -