제출 #1368401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368401		trandkhoa	Evacuation plan (IZhO18_plan)	C++20	100 / 100	815 ms	39688 KiB

plan

/**
 *     Author: Tran Dang Khoa
**/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define FOR(i,l,r) for (int i = (l), _r = (r); i <= _r; i++)
#define REP(i,l,r) for (int i = (l), _r = (r); i < _r; i++)
#define FORN(i,r,l) for (int i = (r), _l = (l); i >= _l; i--)
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define sz(x) (int)x.size()
#define all(v) (v).begin(),(v).end()
#define allVector(v, n) (v).begin() + 1, (v).begin() + (n) + 1
#define segleft (id << 1)
#define segright (id << 1 | 1)
#define tcT template <class T
tcT> bool minimize(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
tcT> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
const int MOD = 1e9+7;

void iofile(string s) {
    freopen((s + ".inp").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

struct infoQuery {
	int a, b;
	
	infoQuery(int _a = 0, int _b = 0) {
		a = _a;
		b = _b;
	}
};

const ll INF = 1e9;
const int N = 1e5 + 1;
vector<pair<int,ll>> edge[N];
vector<int> npp;
vector<ll> dist;
vector<infoQuery> query;
int n, m, k, q;

int checksub() {
	bool flag = true;
	
	for (int i = 1, a, b; i <= q; i++) {
		a = query[i].a, b = query[i].b;
		auto it = lb(all(edge[a]), make_pair(b, -1LL));
		
		if (it -> first != b) {
			flag = false;
			break;
		}
	}
	
	if (n <= 1000 && m <= 1000 && q <= 1000 && flag) {
		return 1;
	} else if (n <= 100000 && q <= 100000 && flag) {
		return 2;
	} else if (n <= 15 && m <= 200 && q <= 200) {
		return 3;
	} else if (q == 1) {
		return 4;
	}
	return 5;
}

struct DisjointSet {
	vector<int> num, par;
	int n;
	
	DisjointSet(int _n) {
		n = _n;
		num.assign(n + 1, 0);
		par.assign(n + 1, 0);
		iota(all(par), 0);
		fill(all(num), 1);
	}
	
	void init() {
		iota(all(par), 0);
		fill(all(num), 1);
	}
	
	int findpar(int u) {
		return (par[u] == u ? u : par[u] = findpar(par[u]));
	}
	
	bool unite(int u, int v) {
		u = findpar(u);
		v = findpar(v);
		if (u == v) return false;
		
		if (num[u] < num[v]) swap(u, v);
		par[v] = u;
		num[u] += num[v];
		return true;
	}
};

void Dijkstra_Root(int st) {
	dist.assign(n + 1, INF);
	dist[st] = 0;
	
	priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
	q.push({0, st});
	
	while (!q.empty()) {
		auto[du, u] = q.top(); q.pop();
		
		if (du > dist[u]) continue;
		
		for (auto[v, w] : edge[u]) {
			if (minimize(dist[v], dist[u] + w)) {
				q.push({dist[v], v});
			}
		}
	}
}

void Dijkstra_Multicore() {
	dist.assign(n + 1, INF);
	priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
	
	for (int u : npp) {
		dist[u] = 0;
		q.push({0, u});
	}
	
	while (!q.empty()) {
		auto[du, u] = q.top(); q.pop();
		
		if (du > dist[u]) continue;
		
		for (auto[v, w] : edge[u]) {
			if (minimize(dist[v], dist[u] + w)) {
				q.push({dist[v], v});
			}
		}
	}
}

namespace subtask1 {
	void solve() {
		for (int i = 1, a, b; i <= q; i++) {
			a = query[i].a, b = query[i].b;
			
			ll ans = INF;
			
			Dijkstra_Root(a);
			for (int u : npp) minimize(ans, dist[u]);
			
			Dijkstra_Root(b);
			for (int u : npp) minimize(ans, dist[u]);
			
			cout << ans << endl;
		}
	}
}

namespace subtask2 {
	void solve() {
		Dijkstra_Multicore();
		
		for (int i = 1, a, b; i <= q; i++) {
			a = query[i].a, b = query[i].b;
			
			cout << min(dist[a], dist[b]) << endl;
		}
	}
}

namespace subtask3 {
	ll ans = -INF;
	
	struct info {
		int u;
		ll used, path_result;
	};
	
	void bfs(int st, int ed) {
		deque<info> q;
		q.pb({st, MASK(st), dist[st]});
		
		while (!q.empty()) {
			info cur = q.front(); q.pop_front();
			
			if (cur.u == ed) {
				maximize(ans, cur.path_result);
				continue;
			}
			
			for (auto[v, w] : edge[cur.u]) {
				if (BIT(cur.used, v)) continue;
				q.pb({v, cur.used | MASK(v), min(cur.path_result, dist[v])});
			}
		}
	}
	
	void solve() {
		Dijkstra_Multicore();
		
		for (int i = 1, a, b; i <= q; i++) {
			a = query[i].a, b = query[i].b;
			
			ans = -INF;
			bfs(a, b);
			
			cout << ans << endl;
		}
	}
}

namespace subtask4 {
	bool check(ll x) {
		DisjointSet dsu(n);
		
		FOR(u, 1, n) {
			if (dist[u] < x) continue;
			
			for (auto[v, w] : edge[u]) {
				if (dist[v] >= x) {
					dsu.unite(u, v);		
				}
			}
		}
		
		return dsu.findpar(query[1].a) == dsu.findpar(query[1].b);
	}
	
	void solve() {
		Dijkstra_Multicore();
		
		ll l = 0, r = INF;
		ll ans;
		
		while (l <= r) {
			ll mid = (l + r) >> 1;
			if (check(mid)) {
				ans = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		
		cout << ans << endl;
	}
}

namespace subtask5 {
	struct infoMid {
		ll mid;
		int u, v, id;
	};
	
	vector<infoMid> canMid;
	
	void solve() {
		Dijkstra_Multicore();
		
		vector<ll> l(q + 1, 0), r(q + 1, INF), ans(q + 1);
		
		vector<int> order(n + 1);
		iota(all(order), 0);
		sort(allVector(order, n), [](int &a, int &b) {
			return dist[a] > dist[b];
		});
		
		DisjointSet dsu(n);
		bool flag = true;
		while (flag) {
			flag = false;
			
			FOR(i, 1, q) {
				if (l[i] > r[i]) continue;
				flag = true;
				ll mid = (l[i] + r[i]) >> 1;
				canMid.pb({mid, query[i].a, query[i].b, i});
			}
			
			if (!flag) break;
			
			sort(all(canMid), [](infoMid &a, infoMid &b) {
				return a.mid > b.mid;
			});
			
			int index = 0;
			
			FOR(i, 1, n) {
				int u = order[i];
				
				for (auto[v, w] : edge[u]) if (dist[v] >= dist[u]) dsu.unite(u, v);
				
				while (index < sz(canMid) && canMid[index].mid > dist[u]) {
					int id = canMid[index].id;
					r[id] = canMid[index].mid - 1;
					index++;
				}
				
				ll nxt = (i < n ? dist[order[i + 1]] : -1);
				while (index < sz(canMid) && canMid[index].mid <= dist[u] && canMid[index].mid > nxt) {
					int id = canMid[index].id;
					if (dsu.findpar(canMid[index].u) == dsu.findpar(canMid[index].v)) {
						ans[id] = canMid[index].mid;
						l[id] = canMid[index].mid + 1;
					} else {
						r[id] = canMid[index].mid - 1;
					}
					index++;
				}
			}
			
			vector<infoMid>().swap(canMid);
			dsu.init();
		}
		
		FOR(i, 1, q) cout << ans[i] << endl;
	}
}

void input() {
	cin >> n >> m;
	
	for (ll i = 1, u, v, w; i <= m; i++) {
		cin >> u >> v >> w;
		edge[u].pb({v, w});
		edge[v].pb({u, w});
	}
	
	// sort edge to lb in checksub
	FOR(i, 1, n) sort(all(edge[i]));
	
	cin >> k;
	for (int i = 1, u; i <= k; i++) {
		cin >> u;
		npp.pb(u);
	}
	
	cin >> q;
	query.assign(q + 1, infoQuery());
	
	for (int i = 1, a, b; i <= q; i++) {
		cin >> a >> b;
		query[i] = {a, b};
	}
}

void trandkhoa() {
	input();	

	// int subtask = checksub();
	
	subtask5::solve();
	
	/*
	switch (subtask) {
		case 1:
			subtask1::solve();
			break;
		case 2:
			subtask2::solve();
			break;
		case 3:
			subtask3::solve();
			break;
		case 4:
			subtask4::solve();
			break;
		default:
			subtask5::solve();
	}
	*/
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //iofile("");
    int test = 1;
    //cin >> test;
    while(test--) trandkhoa();

    return (0 ^ 0);
}

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'void iofile(std::string)':
plan.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen((s + ".inp").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:31:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 10 / 10
• 서브태스크 2: 13 / 13
• 서브태스크 3: 12 / 12
• 서브태스크 4: 19 / 19
• 서브태스크 5: 46 / 46