QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#429282 | #8136. Rebellious Edge | lmeowdn# | WA | 14ms | 11964kb | C++14 | 2.1kb | 2024-06-02 10:45:10 | 2024-06-02 10:45:10 |
Judging History
answer
//Shirasu Azusa 2024.6
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=5e5+5,inf=0x3f3f3f3f3f3f3f3f;
int n,m,g[N],ans,sp,vst[N],id[N],f[N];
struct ed {int u,v,w;} e[N];
void work() {
n=read(), m=read();
rep(i,1,m) {
e[i].u=read(), e[i].v=read(), e[i].w=read();
if(e[i].u>e[i].v) sp=i;
}
ans=0; int root=1;
for(;;) {
rep(i,1,n) g[i]=0; e[0].w=inf;
rep(i,1,m) if(e[i].v!=root&&e[i].v!=e[i].u) {
if(e[g[e[i].v]].w>e[i].w) {
g[e[i].v]=i;
}
}
bool flag=0;
rep(i,1,n) if(i!=root&&g[i]) ans+=e[g[i]].w;
rep(i,1,n) if(i!=root) flag|=(g[i]==sp);
if(!flag) break;
rep(i,1,n) vst[i]=0;
int x=e[sp].u;
while(x&&!vst[x]) vst[x]=1, x=e[g[x]].u;
if(!x) break; int tot=1;
rep(i,1,n) {
if(!vst[i]) id[i]=++tot;
else id[i]=1;
f[i]=e[g[i]].w;
}
rep(i,1,m) {
e[i].w-=f[e[i].v];
e[i].u=id[e[i].u], e[i].v=id[e[i].v];
}
root=id[root]; n=tot;
}
printf("%lld\n",ans);
}
signed main() {
int T=read(); while(T--) work();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11880kb
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: 14ms
memory: 11964kb
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 2493849488 858095911 1034153425 793861088 605832428 1051598350 612891589 1265994009 517769091 1678219738 1556463491 93634961 960978736 984886788 1696503797 1002892611 1969660290 1431417780 1515267731 977157479 1937478556 654475526 1401...
result:
wrong answer 301st numbers differ - expected: '1442045931', found: '1328599284'