Submission #1221267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221267		enzy	Graph (BOI20_graph)	C++20	5 / 100	2 ms	2632 KiB

Graph

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int inf=1e9+7;
vector<pair<int,int>>v[maxn];
int marc[maxn], val[maxn], ja[maxn], sum, at, fim[maxn];
void concluir(int u){
    ja[u]++;
    for(pair<int,int> p : v[u]){
        if(ja[p.first]) continue;
        concluir(p.first);
    }
}
void att(int u){
    marc[u]=at;
    fim[u]=val[u];
    for(pair<int,int> p : v[u]){
        if(marc[p.first]==at) continue;
        att(p.first);
    }
}
bool dfs(int u){
    marc[u]=at;
    sum+=abs(val[u]);
    bool ok=true;
    for(pair<int,int> p : v[u]){
        int nxt=p.second-val[u];
        if(marc[p.first]==at){
            if(nxt!=val[p.first]) ok=false;
        }else{
            val[p.first]=nxt;
            ok=(ok&dfs(p.first));
        }
    }
    return ok;
}
void solve(){
    int n, m; cin >> n >> m;
    for(int i=1;i<=m;i++){
        int a, b, c; cin >> a >> b >> c;
        c*=2;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    for(int i=1;i<=n;i++){
        if(!ja[i]){
            int resp=inf;
            for(int k=0;k<=4;k++){
                sum=0;
                at++;
                val[i]=k;
                if(dfs(i)){
                    if(sum<resp){
                        at++;
                        att(i);
                        resp=sum;
                    }
                }
            }
            if(resp==inf){
                cout << "NO" << endl;
                return;
            }
            concluir(i);
        }
    }
    cout << "YES" << endl;
    for(int i=1;i<=n;i++){
        double x=fim[i];
        x/=2;
        cout << x << " ";
    }
    cout << endl;
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t=1; //cin >> t;
    while(t--) solve();
}

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