QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #540864 | #8941. Even or Odd Spanning Tree | ucup-team4717# | Compile Error | / | / | C++17 | 4.4kb | 2024-08-31 17:59:47 | 2024-08-31 17:59:48 |
Judging History
answer
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-48,ch=getchar();}
return x*f;
}
int T,n,m;
struct Node{
int u,v,w;
}e[N];
int t[N],val[N],f[N],sz[N],cnt,sum,idt;
inline int Find(int x){
return x==f[x]?x:Find(f[x]);
}
vector<pair<int,int> > to[N];
bool cmp(Node a,Node b){
return a.w<b.w;
}
void merge(int x,int y,int X,int Y,int w){
to[X].emplace_back(Y,w);
to[Y].emplace_back(X,w);
if(sz[x]<sz[y]) f[x]=y,sz[y]+=sz[x];
else f[y]=x,sz[x]+=sz[y];
cnt++;
sum+=w;
}
int fa[N],id[N],siz[N],idx;
void dfs(int u,int f){
fa[u]=f,siz[u]=1,id[u]=++idx;
for(pair<int,int> pl:to[u]){
int v=pl.first,w=pl.second;
if(v==f) continue;
val[v]=w;
dfs(v,u);
siz[u]+=siz[v];
}
}
int mn,wdf,sb,s1,s2;
int Fa[N];
int FInd(int x){return x==Fa[x]?x:Fa[x]=FInd(Fa[x]);}
bool flg=0;
void check(int x,int y){
if(x==y) return;
if(!x) return;
if(id[s1]>=id[x]&&id[s1]<=id[x]+siz[x]-1&&id[s2]>=id[x]&&id[s2]<=id[x]+siz[x]-1) return; // if(t[x]>mn) mn=t[x],wdf=val[x];
if((val[x]&1)^(sb&1)){
mn=max(mn,val[x]),flg=1;
Fa[x]=FInd(fa[x]);
}
check(FInd(fa[x]),y);
}
/*
1
5 10
1 5 9
3 2 2
1 3 7
4 5 5
3 2 7
1 1 5
3 2 4
5 2 8
3 1 5
1 2 3
*/
signed main(){
// freopen("j.in","r",stdin);
// freopen("test.out","w",stdout);
T=read();
while(T--){
n=read(),m=read(),cnt=sum=idt=idx=0;
for(int i=1;i<=m;i++){
e[i].u=read();
e[i].v=read();
e[i].w=read();
}
sort(e+1,e+1+m,cmp);
for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
for(int i=1;i<=m;i++){
int x=Find(e[i].u),y=Find(e[i].v);
if(x==y) continue;
merge(x,y,e[i].u,e[i].v,e[i].w);
}
dfs(1,0);
// cout<<cnt<<"\n";
if(cnt<n-1){
printf("-1 -1\n");
for(int i=1;i<=n;i++) t[i]=val[i]=0,to[i].clear();
continue;
}
for(int i=1;i<=n;i++) Fa[i]=i;
int ans1=sum,ans2=1e16;idt=0;
for(int i=1;i<=n;i++) f[i]=i,sz[i]=1,to[i].clear();
for(int i=1;i<=m;i++){
int x=Find(e[i].u),y=Find(e[i].v);
if(x==y){
mn=0;
sb=e[i].w,flg=0;
s1=e[i].u,s2=e[i].v;
check(FInd(e[i].u),1);
check(FInd(e[i].v),1);
if(flg) ans2=min(ans2,ans1-mn+e[i].w);
continue;
}
merge(x,y,e[i].u,e[i].v,e[i].w);
}
if(ans2==1e16) ans2=-1;
if(ans1&1) swap(ans1,ans2);
printf("%lld %lld\n",ans1,ans2);
for(int i=1;i<=n;i++) t[i]=val[i]=0,to[i].clear();
}
return 0;
}
Details
answer.code:22:39: warning: bad option ‘-fwhole-program’ to pragma ‘optimize’ [-Wpragmas]
22 | #pragma GCC optimize("-fwhole-program")
| ^
answer.code:29:41: warning: bad option ‘-fstrict-overflow’ to pragma ‘optimize’ [-Wpragmas]
29 | #pragma GCC optimize("-fstrict-overflow")
| ^
answer.code:31:41: warning: bad option ‘-fcse-skip-blocks’ to pragma ‘optimize’ [-Wpragmas]
31 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
answer.code:45:51: warning: bad option ‘-funsafe-loop-optimizations’ to pragma ‘optimize’ [-Wpragmas]
45 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
answer.code:52:17: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
52 | inline int read(){
| ^
answer.code:52:17: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:52:17: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:52:17: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:65:22: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
65 | inline int Find(int x){
| ^
answer.code:65:22: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:65:22: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:65:22: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:71:23: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
71 | bool cmp(Node a,Node b){
| ^
answer.code:71:23: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:71:23: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:71:23: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:75:41: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
75 | void merge(int x,int y,int X,int Y,int w){
| ^
answer.code:75:41: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:75:41: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:75:41: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:86:21: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
86 | void dfs(int u,int f){
| ^
answer.code:86:21: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:86:21: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:86:21: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:99:15: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
99 | int FInd(int x){return x==Fa[x]?x:Fa[x]=FInd(Fa[x]);}
| ^
answer.code:99:15: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:99:15: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:99:15: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:102:23: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
102 | void check(int x,int y){
| ^
answer.code:102:23: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:102:23: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:102:23: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:129:13: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
129 | signed main(){
| ^
answer.code:129:13: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:129:13: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:129:13: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
In file included from /usr/include/c++/13/string:43,
from /usr/include/c++/13/bitset:52,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
from answer.code:48:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h...