Submission #1221308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221308		enzy	Graph (BOI20_graph)	C++20	58 / 100	648 ms	20408 KiB

Graph

#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3,unrool-loops")
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();
    neg[0].push_back(-inf); neg[1].push_back(-inf);
    pos[0].push_back(inf); pos[1].push_back(inf);
    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>0){
            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-=2;
        }
    }else{ // somo constante negativa, nos cara com prof 0
        while(d<0){
            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+=2;
        }
    }
    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+=c;
        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=-80;k<=80;k++){
                bip=true;
                sum=0;
                at++;
                val[i]=k;
                limpa();
                if(dfs(i)){
                    if(bip) ajeitar();
                    if(sum<resp){
                        at++;
                        att(i);
                        resp=sum;
                        if(bip) break;
                    }
                }
            }
            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();
}

Compilation message (stderr)

Graph.cpp:3:40: warning: bad option '-funrool-loops' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize ("O3,unrool-loops")
      |                                        ^
Graph.cpp:11:12: warning: bad option '-funrool-loops' to attribute 'optimize' [-Wattributes]
   11 | void limpa(){
      |            ^
Graph.cpp:16:20: warning: bad option '-funrool-loops' to attribute 'optimize' [-Wattributes]
   16 | void concluir(int u){
      |                    ^
Graph.cpp:23:15: warning: bad option '-funrool-loops' to attribute 'optimize' [-Wattributes]
   23 | void att(int u){
      |               ^
Graph.cpp:31:15: warning: bad option '-funrool-loops' to attribute 'optimize' [-Wattributes]
   31 | bool dfs(int u){
      |               ^
Graph.cpp:51:14: warning: bad option '-funrool-loops' to attribute 'optimize' [-Wattributes]
   51 | void ajeitar(){
      |              ^
Graph.cpp:82:12: warning: bad option '-funrool-loops' to attribute 'optimize' [-Wattributes]
   82 | void solve(){
      |            ^
Graph.cpp:124:13: warning: bad option '-funrool-loops' to attribute 'optimize' [-Wattributes]
  124 | signed main(){
      |             ^

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