제출 #922030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922030		TAhmed33	Advertisement 2 (JOI23_ho_t2)	C++98	59 / 100	2059 ms	5324 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 25;
int x[MAXN], e[MAXN], n;
bool vis[MAXN];
vector <int> kosaraju;
void dfs (int i) {
	vis[i] = 1;
	for (int j = 1; j <= n; j++) {
		if (abs(x[i] - x[j]) <= e[i] - e[j] && !vis[j]) {
			dfs(j);
		}
	}
	kosaraju.push_back(i);
}
int comp[MAXN], cnt;
void dfs2 (int i, int c) {
	comp[i] = c; vis[i] = 1;
	for (int j = 1; j <= n; j++) {
		if (abs(x[j] - x[i]) <= e[j] - e[i] && !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++) {
		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 (int j = 1; j <= n; j++) {
			if (comp[j] == comp[i]) continue;
			if (abs(x[i] - x[j]) <= e[i] - e[j]) deg[j]++;
		}
	}
	int ans = 0;
	for (int i = 1; i <= cnt; i++) if (!deg[i]) {
		ans++;
	}
	cout << ans << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 0 / 31