Submission #1221288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221288		enzy	Graph (BOI20_graph)	C++20	58 / 100	385 ms	17196 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];
vector<int>neg[2], pos[2], ids;
int marc[maxn], val[maxn], ja[maxn], sum, at, fim[maxn], prof[maxn];
bool bip;
void limpa(){
    neg[0].clear(); neg[1].clear();
    pos[0].clear(); pos[1].clear();
    ids.clear();
}
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;
    if(val[u]<0) neg[prof[u]%2].push_back(val[u]);
    else pos[prof[u]%2].push_back(val[u]);
    ids.push_back(u);
    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;
            if(prof[u]%2==prof[p.first]%2) bip=false;
        }else{
            val[p.first]=nxt;
            prof[p.first]=prof[u]+1;
            ok=(ok&dfs(p.first));
        }
    }
    return ok;
}
void ajeitar(){
    int d=neg[0].size()-neg[1].size()+pos[1].size()-pos[0].size();
    sort(neg[0].begin(),neg[0].end());
    sort(neg[1].begin(),neg[1].end());
    sort(pos[0].begin(),pos[0].end()); reverse(pos[0].begin(),pos[0].end());
    sort(pos[1].begin(),pos[1].end()); reverse(pos[1].begin(),pos[1].end());
    int lst=0;
    if(d>0){ // somo constante positiva, nos cara com prof 0
        while(d){
            lst=min(abs(neg[0].back()),pos[1].back());
            if(abs(neg[0].back())<pos[1].back()) neg[0].pop_back();
            else pos[1].pop_back();
            d--;
        }
    }else{ // somo constante negativa, nos cara com prof 0
        while(d){
            lst=-min(abs(neg[1].back()),pos[0].back());
            if(abs(neg[1].back())<pos[0].back()) neg[1].pop_back();
            else pos[0].pop_back();
            d++;
        }
    }
    sum=0;
    for(int a : ids){
        if(prof[a]%2) val[a]-=lst;
        else val[a]+=lst;
        sum+=abs(val[a]);
    }
}
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;
            bool eh=false;
            for(int k=-52;k<=52;k++){
                bip=true;
                sum=0;
                at++;
                val[i]=k;
                limpa();
                if(dfs(i)){
                    /*cout << sum << ": ";
                    for(int i=1;i<=n;i++) cout << val[i] << " ";
                    cout << endl;
                    if(bip) ajeitar();
                    cout << sum << ": ";
                    for(int i=1;i<=n;i++) cout << val[i] << " ";
                    cout << endl;
                    cout << endl;*/
                    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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 24 / 24
• Subtask 4: 0 / 42
• Subtask 5: 5 / 5