제출 #1234072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234072		nguyenphong233	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	683 ms	137856 KiB

bitaro

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)1e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;
const int BASE = 100;

int n,m,q;
vector<int> adj[MAX];
int dd[MAX][2];
vector<ii> lenx[MAX];
int mp[MAX];
int dist[MAX];

void solve(int s,int times){
	for(int i = 1;i <= s;i++){
		dist[i] = 0;
		for(auto v : adj[i]){
			dist[i] = max(dist[v] + 1,dist[i]);
		}
		if(dist[i] == 0 && mp[i] == times)dist[i] = -1;
	}
	cout << dist[s] << '\n';
}
signed main(){
	
	read();
	cin >> n >> m >> q;
	
	for(int i = 1,u,v;i <= m;i++){
		cin >> u >> v;
		adj[v].push_back(u);
	}	
	
	for(int i = 1;i <= n;i++){
		dd[i][0] = 0;
		dd[i][1] = i;
		vector<int> cur;
		cur.push_back(i);

		for(auto v : adj[i]){
			for(auto e : lenx[v]){
				int p = e.Y;
				if(dd[p][1] != i){
					dd[p][1] = i;
					dd[p][0] = -e.X + 1;
					cur.push_back(p);
				}else{
					dd[p][0] = max(dd[p][0],-e.X + 1);
				}
			}
		}
		
		for(auto v : cur)lenx[i].push_back({-dd[v][0],v});
		sort(lenx[i].begin(),lenx[i].end());
		
		while(lenx[i].size() > BASE)lenx[i].pop_back();
		// cout << i << " :\n";
		// for(auto v : lenx[i])cout << -v.X << " " << v.Y << '\n';
	}
	
	for(int i = 1;i <= q;i++){
		int t,y;
		cin >> t >> y;
		for(int j = 1,u;j <= y;j++){
			cin >> u;
			mp[u] = i;
		}
		if(y >= BASE)solve(t,i);
		else {
			bool ok = 0;
			for(auto v : lenx[t]){
				if(mp[v.Y] != i){
					cout << -v.X << "\n";
					ok = 1;
					break;
				} 
			}
			if(!ok)cout << "-1\n";
		}
	}
	
	
}

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