QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#651297#8941. Even or Odd Spanning TreeYoshinow2001#WA 136ms3568kbC++203.6kb2024-10-18 17:35:252024-10-18 17:35:27

Judging History

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

  • [2024-10-18 17:35:27]
  • 评测
  • 测评结果:WA
  • 用时:136ms
  • 内存:3568kb
  • [2024-10-18 17:35:25]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
struct DSU{
    vector<int> fa;
    void init(int n){fa.resize(n+1);rep(i,1,n)fa[i]=i;}
    int find(int x){
        if(fa[x]==x)return x;
        return fa[x]=find(fa[x]);
    }
    void merge(int x,int y){
        int fx=find(x),fy=find(y);
        fa[fy]=fx;
    }
};
vector<vector<int>> G;
vector<int> fa,sz,son,dep,top;
vector<int> a[2],f[2][20],par[20];
void dfs1(int x){
    sz[x]=1;
    for(auto to:G[x])if(to!=fa[x]){
        fa[to]=x;
        dep[to]=dep[x]+1;
        dfs1(to);
        sz[x]+=sz[to];
        if(sz[to]>sz[son[x]])son[x]=to;
    }
}
void dfs2(int x,int t){
    top[x]=t;
    if(son[x])dfs2(son[x],t);
    for(auto to:G[x])if(to!=son[x]&&to!=fa[x])dfs2(to,to);
}
int lca(int a,int b){
    while(top[a]!=top[b]){
        if(dep[top[a]]<dep[top[b]])swap(a,b);
        a=fa[top[a]];
    }
    if(dep[a]<dep[b])swap(a,b);
    return b;
}

void solve(){
    int n,m;
    cin>>n>>m;
    fa=sz=son=dep=top=vector<int> (n+1);
    G=vector<vector<int>>(n+1);
    a[0]=vector<int>(n+1,-1);
    a[1]=vector<int>(n+1,-1);
    rep(odd,0,1)rep(d,0,19)f[odd][d]=vector<int>(n+1,0);
    rep(d,0,19)par[d]=vector<int>(n+1,0);
    
    DSU dsu;dsu.init(n);
    vector<array<int,3>> E;
    rep(i,1,m){
        int u,v,w;
        cin>>u>>v>>w;
        E.push_back({w,u,v});
    }
    sort(E.begin(),E.end());
    vector<bool> used(m);
    long long sum=0;
    for(int i=0;i<m;i++){
        auto [w,u,v]=E[i];
        if(dsu.find(u)==dsu.find(v))continue;
        G[u].push_back(v);
        G[v].push_back(u);
        dsu.merge(u,v);
        sum+=w;
        used[i]=true;
    }
    int block=0;
    rep(i,1,n)if(dsu.find(i)==i)block++;
    if(block!=1){
        cout<<-1<<' '<<-1<<endl;
        return;
    }
    long long ans[2];
    int p=(sum&1);
    // cout<<"sum="<<sum<<endl;
    ans[p]=sum;ans[p^1]=std::numeric_limits<long long>::max();
    dfs1(1);dfs2(1,1);//fa[1]=0;
    
    for(int i=0;i<m;i++){
        if(used[i]){
            auto [w,u,v]=E[i];
            if(fa[u]==v)a[w&1][u]=w;
            else a[w&1][v]=w;
        }
    }
    rep(i,1,n)rep(o,0,1)f[o][0][i]=a[o][i];
    rep(i,1,n)par[0][i]=fa[i];
    
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            par[j][i]=par[j-1][par[j-1][i]];
            for(int o=0;o<=1;o++)f[o][j][i]=max(f[o][j-1][i],f[o][j-1][par[j-1][i]]);
        }
    }
    auto calc=[&](int a,int b,int o){//a to b
        int v=dep[a]-dep[b],ans=-1;
        v--;
        for(int j=19;j>=0;j--){
            if(v>=(1<<j)){
                ans=max(ans,f[o][j][a]);
                a=par[j][a];
                v-=(1<<j);
            }
        }
        ans=max(ans,f[o][0][a]);
        return ans;
    };
    // cout<<"fa:";rep(i,1,n)cout<<fa[i]<<' ';cout<<endl;
    // cout<<"fa:";rep(i,1,n)cout<<top[i]<<' ';cout<<endl;

    for(int i=0;i<m;i++){
        if(!used[i]){
            auto [w,u,v]=E[i];
            // cout<<"work on "<<u<<' '<<v<<endl;
            int L=lca(u,v);
            // cout<<"L="<<L<<endl;
            int mx=max(calc(u,L,(w&1)^1),calc(v,L,(w&1)^1));
            if(mx!=-1)ans[p^1]=min(ans[p^1],ans[p]+w-mx);
        }
    }
    if(ans[p^1]==std::numeric_limits<long long>::max())ans[p^1]=-1;
    cout<<ans[0]<<' '<<ans[1]<<endl;
}
int main(){
    fastio;
    int tc;cin>>tc;
    while(tc--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
2 1
1 2 5
3 1
1 3 1
4 4
1 2 1
1 3 1
1 4 1
2 4 2

output:

-1 5
-1 -1
4 3

result:

ok 6 numbers

Test #2:

score: -100
Wrong Answer
time: 136ms
memory: 3568kb

input:

10000
16 50
1 2 649251632
2 3 605963017
3 4 897721528
4 5 82446151
5 6 917109168
6 7 79647183
7 8 278566178
7 9 573504723
3 10 679859251
8 11 563113083
1 12 843328546
10 13 594049160
11 14 997882839
7 15 569431750
2 16 244494799
16 7 960172373
13 4 317888322
13 3 446883598
9 3 678142319
5 8 43208692...

output:

3140067932 3159441841
1262790434 1309454727
1263932600 1307926149
1189242112 1180186165
2248358640 2173083215
3776889482 3738936375
1093500444 1058677117
3433711014 3402127725
1201099898 1187873655
1395482806 1410162043
3456885934 3486092007
3943951826 3988876469
2479987500 2494911351
2909126794 284...

result:

wrong answer 10th numbers differ - expected: '2261370885', found: '2173083215'