Submission #8401265


Source Code Expand

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

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef pair<ll, ll> pll;

const ll MAXN = 2 * 100 * 1000 + 17, mod = 1e9 + 7, inf = 2e16 + 17;

ll n, m, s, t, ds[MAXN], dt[MAXN], cnts[MAXN], cntt[MAXN], ans;
pair<pll, ll> edge[MAXN];
vector<pll> adj[MAXN];

void dijs() {
	fill(ds + 1, ds + n + 1, inf);
	set<pll> st;
	st.insert({0, s});
	ds[s] = 0;
	cnts[s] = 1;
	while (!st.empty()) {
		int u = st.begin() -> ss;
		st.erase(st.begin());
		for (auto i : adj[u]) {
			if (ds[i.ff] > ds[u] + i.ss) {
				st.erase({ds[i.ff], i.ff});
				ds[i.ff] = ds[u] + i.ss;
				cnts[i.ff] = 0;
				st.insert({ds[i.ff], i.ff});
			}
			if (ds[i.ff] == ds[u] + i.ss)
				(cnts[i.ff] += cnts[u]) %= mod;
		}

	}
}

void dijt() {
	fill(dt + 1, dt + n + 1, inf);
	set<pll> st;
	st.insert({0, t});
	dt[t] = 0;
	cntt[t] = 1;
	while (!st.empty()) {
		int u = st.begin() -> ss;
		st.erase(st.begin());
		for (auto i : adj[u]) {
			if (dt[i.ff] > dt[u] + i.ss) {
				st.erase({dt[i.ff], i.ff});
				dt[i.ff] = dt[u] + i.ss;
				cntt[i.ff] = 0;
				st.insert({dt[i.ff], i.ff});
			}
			if (dt[i.ff] == dt[u] + i.ss)
				(cntt[i.ff] += cntt[u]) %= mod;
		}

	}
}


int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	cin >> s >> t;
	for (int i = 1; i <= m; i++) {
		int v, u, w;
		cin >> v >> u >> w;
		adj[v].pb({u, w});
		adj[u].pb({v, w});
		edge[i] = {{u, v}, w};

	}
	dijs();
	dijt();
	if (cnts[t] == 0)
		return cout << 0 << endl, 0;
	ans = (cnts[t] * cntt[s]) % mod;
	for (int i = 1; i <= m; i++) {
		int x = edge[i].ff.ff, y = edge[i].ff.ss;
		if (cnts[x] == 0 || cntt[x] == 0)
			continue;
		if (ds[x] + dt[y] + edge[i].ss == ds[t] && abs(ds[x] - dt[y]) < edge[i].ss)
			(ans -= (cnts[x] * cntt[y]) % mod) %= mod;
		if (ds[y] + dt[x] + edge[i].ss == ds[t] && abs(ds[y] - dt[x]) < edge[i].ss)
			(ans -= (cnts[y] * cntt[x]) % mod) %= mod;
	}
	for (int i = 1; i <= n; i++)
		if (cnts[i] != 0 && ds[i] + dt[i] == ds[t] && ds[i] == dt[i])
			(ans = ans - ((cnts[i] * cntt[i]) % mod)) %= mod;
	while (ans < 0) {
		ans += mod;
		ans %= mod;
	}
	cout << ans % mod << endl;
	return 0;
}

Submission Info

Submission Time
Task E - Avoiding Collision
User Fype
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2290 Byte
Status WA
Exec Time 239 ms
Memory 30576 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 4
AC × 8
WA × 14
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt, sample04.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, sample01.txt, sample02.txt, sample03.txt, sample04.txt
Case Name Status Exec Time Memory
01.txt AC 195 ms 30576 KB
02.txt AC 239 ms 27648 KB
03.txt WA 190 ms 25856 KB
04.txt WA 183 ms 25600 KB
05.txt WA 225 ms 27520 KB
06.txt WA 129 ms 23168 KB
07.txt WA 180 ms 27264 KB
08.txt WA 77 ms 20352 KB
09.txt WA 182 ms 25856 KB
10.txt WA 190 ms 25856 KB
11.txt AC 212 ms 25856 KB
12.txt AC 205 ms 25600 KB
13.txt WA 201 ms 27264 KB
14.txt WA 211 ms 27264 KB
15.txt WA 202 ms 27264 KB
16.txt WA 200 ms 27264 KB
17.txt WA 204 ms 27264 KB
18.txt WA 199 ms 27264 KB
sample01.txt AC 5 ms 12544 KB
sample02.txt AC 4 ms 12544 KB
sample03.txt AC 5 ms 12544 KB
sample04.txt AC 5 ms 12544 KB