Submission #73500767

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using i128 = __int128;
using u128 = unsigned __int128;

mt19937_64 mrand((u64)random_device{}() << 32 ^ random_device{}() ^
	chrono::high_resolution_clock::now().time_since_epoch().count());
template<class T = i64,class T2>T rnd(T l,T2 r){
return uniform_int_distribution<T>(l,r)(mrand);}

int main (){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);


	int n,m;
	cin >> n >> m;

	vector<vector<int>> a(n + 1);
	vector<int> tag(n + 1);
	vector<int> vis(n + 1,1e9);

	for (;m--;){
		int x,y;
		cin >> x >> y;

		a[x].push_back(y);
	}

	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;

	vis[1] = 1;
	q.emplace(1,1);

	for (;!q.empty();){
		auto [x,y] = q.top();
		q.pop();

		if (vis[y] != x) continue;

		for (auto i:a[y])
			if (max(x,i) < vis[i])
				q.emplace(vis[i] = max(x,i),i);
	}

	int ma = 0,cnt = 0;

	for (int i = 1;i <= n;i++){
		ma = max(ma,vis[i]);
		cnt -= tag[i];

		for (auto j:a[i])
			if (j > i&&!tag[j])
				cnt++,tag[j] = 1;

		if (ma > i){
			cout << "-1\n";
			continue;
		}

		cout << cnt << '\n';
	}
}

Submission Info

Judge Result