Submission #906779

#	Time	Username	Problem	Language	Result	Execution time	Memory
906779		Darren0724	Graph (BOI20_graph)	C++17	100 / 100	94 ms	24800 KiB

Graph

#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
namespace {
const int N=200005;
const int INF=1e9;
int n,m;
vector<pair<int,int>> adj[N];
vector<int> a(N),b(N),vis(N),ans(N),rec; //ax+b
int x=INF;
void dfs(int k){
    vis[k]=1;
    rec.push_back(k);
    for(auto [e,f]:adj[k]){
        if(!vis[e]){
            a[e]=-a[k];
            b[e]=f-b[k];
            dfs(e);
        }
        else{
            int a1=-a[k];
            int b1=f-b[k];
            if((a1==a[e]&&b1!=b[e])){
                cout<<"NO"<<endl;
                exit(0);
            }
            if(a1!=a[e]){
                int x1=(b1-b[e])/(a[e]-a1);
                if(x==INF){
                    x=x1;
                }
                else if(x!=x1){
                    cout<<"NO"<<endl;
                    exit(0);
                }
            }
        }
    }

}
int32_t main1() {
    LCBorz;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        adj[a].push_back({b,c<<1});
        adj[b].push_back({a,c<<1});
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            x=INF;
            a[i]=1;
            rec.clear();
            dfs(i);
            if(x==INF){
                vector<int> t;
                for(int j:rec){
                    t.push_back(-a[j]*b[j]);
                }
                sort(all(t));
                int sz=rec.size();
                x=t[sz/2];
            }
            for(int j:rec){
                ans[j]=a[j]*x+b[j];
            }
            
        }
    }
    cout<<"YES"<<endl;
    for(int i=1;i<=n;i++){
        if(ans[i]<0){
            cout<<'-';
        }
        cout<<abs(ans[i])/2<<'.'<<(ans[i]&1)*5<<' ';
    }
    cout<<endl;

    return 0;
}
}
int main(){
    main1();
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42