제출 #922029

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

Main

#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';
}

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