oj.uz

Submission #906776

# Submission time Handle Problem Language Result Execution time Memory
906776 2024-01-15T01:19:38 Z Darren0724 Graph (BOI20_graph) C++17
0 / 100
 4 ms 11352 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=200005;
const int INF=1e18;
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 main() {
    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];
                }
                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<<ans[i]/2<<"."<<(ans[i]&1)*5<<' ';
    }
    cout<<endl;

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11352 KB Sum of endpoints for edge (1; 2) differs from the expected value 1.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11352 KB Sum of endpoints for edge (1; 2) differs from the expected value 1.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11352 KB Sum of endpoints for edge (1; 2) differs from the expected value 1.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11352 KB Sum of endpoints for edge (1; 2) differs from the expected value 1.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11352 KB Sum of endpoints for edge (1; 2) differs from the expected value 1.
2 Halted 0 ms 0 KB -