QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#288009#5048. All Pair Maximum Flowzhangtx123WA 4ms22540kbC++142.4kb2023-12-21 15:18:522023-12-21 15:18:53

Judging History

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

  • [2023-12-21 15:18:53]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:22540kb
  • [2023-12-21 15:18:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 400010
int n, m, i, j, k, T;
int sze[N], f[N], u[N], v[N], w[N]; 
int lst, nw, vis[N], ans, x, y; 
set<pair<int, int> >G[N], conv; 
vector<pair<int, int> >E; 

int fa(int x) {
	if(f[x] == x) return x; 
	return f[x] = fa(f[x]); 
}

void del(int i) {
	conv.erase({w[i], i}); 
	G[u[i]].erase({v[i], i}); 
	G[v[i]].erase({u[i], i}); 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); 
	for(i=1; i<=m; ++i) {
		u[i]=read(); v[i]=read(); w[i]=read(); 
		if(u[i] > v[i]) swap(u[i], v[i]); 
		if(v[i]==u[i]+1 || (u[i]==1 && v[i]==n)) conv.insert({w[i], i}), debug("{%lld %lld}\n", w[i], i); 
		if(u[i]==1 && v[i]==n) swap(u[i], v[i]); 
		G[u[i]].insert({v[i], i}); 
		G[v[i]].insert({u[i], i}); 
	}
	while(!conv.empty()) {
		auto t = *conv.begin(); 
		vis[i=t.se]=1; del(i); 
		lst=v[i]; nw=u[i]; 
		debug(">> %lld | %lld %lld\n", i, u[i], v[i]); 
		while(nw!=v[i]) {
			debug("%lld %lld\n", lst, nw); 
			auto it = G[nw].upper_bound({lst, 1e9}); 
			if(it == G[nw].end()) it = G[nw].begin(); 
			j = it -> se; 
			if(conv.find({w[j], j})==conv.end()) {
				debug("============= {%lld %lld}\n", w[j], j); 
				w[j] += w[i];  
				conv.insert({w[j], j}); 
				if(u[j] != nw) swap(u[j], v[j]); 
			}
			else del(j), w[j]+=w[i]; 
			debug("find edge(%lld) : %lld -> %lld {%lld %lld}\n", j, v[j], u[j]); 
			lst = nw; nw = it->fi; 
		}
	}
	for(i=1; i<=n; ++i) f[i]=i, sze[i]=1; 
	for(i=1; i<=m; ++i) 
		if(!vis[i]) E.pb({w[i], i}), debug("Add %lld [%lld %lld]\n", w[i], u[i], v[i]);
	sort(E.begin(), E.end()); reverse(E.begin(), E.end()); 
	for(auto t : E) {
		i = t.se; 
		x = u[i]; y = v[i]; 
		ans += sze[fa(x)]*sze[fa(y)]*w[i]; 
		debug("%lld <-> %lld %lld %lld %lld[%lld %lld] \n", x, y, w[i], fa(x), fa(y), sze[fa(x)], sze[fa(y)]); 
		sze[fa(y)]+=sze[fa(x)]; f[fa(x)]=fa(y); 
	}
	printf("%lld", ans); 
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 22400kb

input:

6 8
1 2 1
2 3 10
3 4 100
4 5 1000
5 6 10000
6 1 100000
1 4 1000000
1 5 10000000

output:

12343461

result:

ok 1 number(s): "12343461"

Test #2:

score: -100
Wrong Answer
time: 4ms
memory: 22540kb

input:

20 30
5 7 9066926
13 15 636587393
1 12 234024833
7 11 863853881
7 9 961926707
12 20 525748907
7 10 217196987
15 20 715248370
17 19 577652480
16 19 78750484
1 2 216519168
2 3 26083428
3 4 381598120
4 5 78513523
5 6 106643887
6 7 20069507
7 8 467260856
8 9 383736316
9 10 400897545
10 11 404258163
11 1...

output:

101681004988

result:

wrong answer 1st numbers differ - expected: '858325335', found: '101681004988'