Submission #922029

#TimeUsernameProblemLanguageResultExecution timeMemory
922029TAhmed33Advertisement 2 (JOI23_ho_t2)C++98
59 / 100
2078 ms32604 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 25;
int x[MAXN], e[MAXN], n;
vector <int> adj[MAXN], radj[MAXN];
bool vis[MAXN];
vector <int> kosaraju;
void dfs (int pos) {
	vis[pos] = 1;
	for (auto j : adj[pos]) {
		if (!vis[j]) dfs(j);
	}
	kosaraju.push_back(pos);
}
int comp[MAXN], cnt;
void dfs2 (int pos, int c) {
	comp[pos] = c; vis[pos] = 1;
	for (auto j : radj[pos]) {
		if (!vis[j]) {
			dfs2(j, c);
		}
	}
}
int deg[MAXN];
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n; 
	for (int i = 1; i <= n; i++) cin >> x[i] >> e[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			if (abs(x[i] - x[j]) <= e[i] - e[j]) {
				adj[i].push_back(j);
				radj[j].push_back(i);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) dfs(i);
	}
	reverse(kosaraju.begin(), kosaraju.end());
	memset(vis, 0, sizeof(vis));
	for (auto i : kosaraju) {
		if (!vis[i]) {
			dfs2(i, ++cnt);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (auto j : adj[i]) {
			if (comp[j] == comp[i]) continue;
			deg[j]++;
		}
	}
	int ans = 0;
	for (int i = 1; i <= cnt; i++) if (!deg[i]) {
		ans++;
	}
	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...