QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#325969#8136. Rebellious EdgefryanWA 55ms3876kbC++232.2kb2024-02-12 06:16:202024-02-13 03:05:13

Judging History

你现在查看的是最新测评结果

  • [2024-02-13 03:05:13]
  • 管理员手动重测该提交记录
  • 测评结果:WA
  • 用时:55ms
  • 内存:3876kb
  • [2024-02-12 06:16:20]
  • 提交

answer

#pragma GCC optimize("trapv")
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
using namespace std;
#define int long long
#define P pair
#define pi P<int,int>
#define ff first
#define ss second
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define V vector
#define vi V<int>
#define v2i V<vi>
#define v3i V<v2i>
#define vpi V<pi>
#define vb V<bool>
#define v2b V<vb>
#define pb push_back
#define S set
#define si S<int>
#define ins insert
#define era erase
#define M map
#define mii M<int,int>
#define Q queue
#define PQ priority_queue
const int MOD=998244353;
const int INF=1e9;
int smax(int& a, int b) {return a = max(a,b);}
int smin(int& a, int b) {return a = min(a,b);}

struct PFX {
	vector<int> pre;
	PFX(vector<int>& arr) {
		pre = vector<int>(arr.size()+1, 0);
		for (int i = 1; i <= arr.size(); i++) {
			pre[i] = pre[i-1] + arr[i-1];
		}
	}
	int RSQ(int l, int r) {
		if (l > r) return 0;
		return pre[r+1]-pre[l];
	}
};

int n, m, a, b, c;
V<vpi> adj;
V<vpi> rdj;
vi md;

void solve() {
	adj.clear();
	cin >> n >> m; adj = V<vpi>(n); rdj = V<vpi>(n); md = vi(n, INF);
	for (int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w; --u; --v;
		if (u > v) {
			a = v; b = u; c = w;
		} else {
			adj[u].pb(mp(v,w));
			rdj[v].pb(mp(u,w));
			smin(md[v],w);
		}
	}
	vi afg(n, INF);
	afg[0] = 0;
	for (int i = 1; i < n; i++) {
		afg[i] = md[i] + afg[i-1];
	}
	md[a] = 0;
	PFX ad(md);
	vi dp(n,INF); dp[0] = 0;
	for (int i = 1; i <= b; i++) {
		if (i == a) continue;
		for (auto e : rdj[i]) {
			if (e.ff == a) continue;
			smin(dp[i],dp[e.ff] + e.ss + ad.RSQ(e.ff+1,i-1));
		}
	}
	cout << min(afg[n-1],dp[b]+ad.RSQ(b+1,n-1)+c) << "\n";
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int t; cin >> t;
	while (t--) solve();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3564kb

input:

3
5 6
1 2 4
1 3 2
2 3 0
3 4 1
4 5 1
5 2 1
4 4
1 2 4
1 3 6
1 4 8
4 2 1000000
3 3
1 2 100
2 1 10
2 3 1000

output:

5
18
1100

result:

ok 3 number(s): "5 18 1100"

Test #2:

score: -100
Wrong Answer
time: 55ms
memory: 3876kb

input:

50000
4 5
2 4 998973548
2 3 501271695
4 1 778395982
1 4 32454891
1 2 757288934
4 5
1 4 720856669
2 3 665098951
3 4 407461517
2 1 866914401
1 2 457859826
4 5
1 2 75288664
1 4 624893594
3 2 458973866
2 4 769074655
2 3 834773751
4 5
2 3 237060634
2 4 297307882
3 4 200383586
1 2 42856502
3 1 16574713
4 ...

output:

1291015520
1530420294
1534956009
480300722
1366795927
1541095843
1720144946
858095911
1034153425
793861088
605832428
1051598350
612891589
1265994009
517769091
1678219738
1556463491
93634961
960978736
984886788
1696503797
1002892611
1929526571
1263064938
1515267731
977157479
1937478556
654475526
1401...

result:

wrong answer 7th numbers differ - expected: '2493849488', found: '1720144946'