제출 #735620

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

bitaro

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const ll MOD = 1e9 + 7;
const double EPS = 1e-7;
const int MAX = (int)1e5 + 10;
const double PI = acos(-1);

vector<int> adj[MAX];
vector<int> par[MAX];

vector<pair<int, int> > shits[MAX];
int frq[MAX] ;

bool removed[MAX];
int sqrt_n = 400;

void build(queue<int> q, vector<int> ind){
	while(!q.empty()){
		int curNode = q.front();
		q.pop(); 

		for(auto node : adj[curNode]){
			ind[node]--;
			if(ind[node] == 0) q.push(node); 
		}

		vector<pair<int,int> > &res = shits[curNode]; 
		res.push_back({0, curNode}); 
		for(auto node : par[curNode]){
			for(auto x : shits[node]){
				frq[x.second] = max(frq[x.second], x.first + 1);
			}
		}
		for(auto node : par[curNode]){
			for(auto x : shits[node]){
				if(frq[x.second] > 0){
					res.push_back({frq[x.second], x.second});
					frq[x.second] = 0 ;
				}
			}
		}
		sort(res.rbegin(), res.rend()) ;
		while((int)res.size() > sqrt_n){
			res.pop_back(); 
		}
		// cout << curNode << endl; 
		// for(auto x : res) cout << x.first << " " << x.second << endl ;
	}
}

int bfs(queue<int> q, vector<int> ind, int n, int nodeParty)
{
	vector<int> dis(n+1,0); 
	while (!q.empty())
	{
		int curNode = q.front(); 
		q.pop();
		for(auto node : adj[curNode]){
			ind[node]-- ;
			if(ind[node] == 0) q.push(node); 
			if(dis[curNode] == 0 && removed[curNode] == true) continue ;
			dis[node] = max(dis[node], dis[curNode] + 1);
		}

	}
	return dis[nodeParty];
	
}

void solve()
{
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> ind(n + 1, 0); 
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		par[v].push_back(u);
		ind[v]++;
	}
	queue<int> roots;
	for (int i = 1; i <= n; i++)
	{
		if (ind[i] == 0) roots.push(i) ;
	}

	build(roots, ind); 
	
	while (q--)
	{
		int nodeParty, totalRemoved;
		vector<int> rmv;
		cin >> nodeParty >> totalRemoved;
		for (int i = 1; i <= totalRemoved; i++)
		{
			int node;
			cin >> node;
			rmv.push_back(node);
		}
		for(auto node : rmv) removed[node] = true ;

		int sz = (int)rmv.size();
		int ans = -1;
		if (sz > sqrt_n)
		{ // FIRST TYPE OF QUESRIES
			ans = bfs(roots, ind, n, nodeParty);  
		}
		else
		{
			for(auto node : shits[nodeParty]){
				if(removed[node.second] == false){
					ans = max(ans,node.first); 
				}
			}
		}
		if(ans == 0 && removed[nodeParty] == true) ans = -1;
		cout << ans << endl ;
		for(auto node : rmv) removed[node] = false ;

	}
}
int main()
{
	IOS;
	solve();

	return 0;
}

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