Submission #164030

#	Time	Username	Problem	Language	Result	Execution time	Memory
164030		oolimry	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	27 ms	19832 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;

struct query{
	int id;
	unordered_set<int> cannot;
};
static set<ii, greater<ii> > dp[100005];
static unordered_map<int,int> mm;
static int offset[100005]; ///dp[i] + offset[i] = actual value
static vi adj[100005];
static int answer[100005];
static vector<query> queries[100005];
int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	
	int n, m, q;
	cin >> n >> m >> q;
	
	for(int i = 0;i < m;i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[b].push_back(a);
	}
	
	for(int qq = 0;qq < q;qq++){
		int y, t;
		cin >> y >> t;
		y--;
		query nQ;
		nQ.id = qq;
		for(int i = 0;i < t;i++){
			int x;
			cin >> x;
			x--;
			nQ.cannot.insert(x);
		}
		queries[y].push_back(nQ);
	}
	
	for(int u = 0;u < n;u++){
		dp[u].insert(ii(0-offset[u],u));
		
		for(int v : adj[u]){
			bool isSwap = false;
			vector<ii> ori;
			int orioff = 0;
			
			
			if(dp[u].size() < dp[v].size()){
				isSwap = true;
				swap(dp[u],dp[v]);
				swap(offset[u],offset[v]);
				offset[u]++;
				offset[v]--;
			}
			
			for(ii x : dp[v]){
				long long value = x.first+1+offset[v]-offset[u]; 
				if(mm.find(x.second) != mm.end()){
					if(mm[x.second] < value){
						dp[u].insert(ii(value,x.second));
						dp[u].erase(dp[u].find(ii(mm[x.second],x.second)));
						mm[x.second] = value;
					}
				}
				else{
					mm[x.second] = value;
					dp[u].insert(ii(value,x.second));
				}
			}
			if(isSwap){
				dp[v].clear();
				for(ii x : ori) dp[v].insert(x);
				offset[v] = orioff;
			}
		}
		mm.clear();
		for(query qq : queries[u]){
			bool can = false;
			for(ii x : dp[u]){
				if(qq.cannot.find(x.second) == qq.cannot.end()){
					answer[qq.id] = x.first + offset[u];
					can = true;
					break;
				}
			}
			if(!can) answer[qq.id] = -1;
		}
		/*
		for(ii x : dp[u]){
			cout << "(" << x.first + offset[u] << ", " << x.second << ") ";
		}
		cout << offset[u] << "\n";
		//*/
	}
	
	for(int i = 0;i < q;i++){
		cout << answer[i] << "\n";
	}
	
	
	
	
}

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