Submission #8401210


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 int MAXN = 2 * 100 * 1000 + 17, mod = 1e9 + 7, inf = 1e9 + 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();
	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 (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 (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 2169 Byte
Status WA
Exec Time 263 ms
Memory 30576 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 4
AC × 9
WA × 13
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 210 ms 30576 KB
02.txt AC 263 ms 27648 KB
03.txt WA 136 ms 25600 KB
04.txt WA 132 ms 25472 KB
05.txt WA 252 ms 27520 KB
06.txt WA 104 ms 23040 KB
07.txt WA 216 ms 27264 KB
08.txt AC 58 ms 20352 KB
09.txt WA 141 ms 25728 KB
10.txt WA 135 ms 25728 KB
11.txt AC 146 ms 25472 KB
12.txt AC 144 ms 25472 KB
13.txt WA 201 ms 27264 KB
14.txt WA 208 ms 27264 KB
15.txt WA 249 ms 27264 KB
16.txt WA 235 ms 27264 KB
17.txt WA 241 ms 27264 KB
18.txt WA 234 ms 27264 KB
sample01.txt AC 5 ms 12544 KB
sample02.txt AC 5 ms 12544 KB
sample03.txt AC 4 ms 12544 KB
sample04.txt AC 4 ms 12544 KB