Submission #1204644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204644		Unforgettablepl	Graph (BOI20_graph)	C++20	100 / 100	94 ms	25536 KiB

Graph

// #pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long

const long double epsilon = 1e-10;

struct constrains{
    int k;
    int vSign;
    constrains():k(0),vSign(1){}
    constrains(int a,int b):k(a),vSign(b){}
    constrains(constrains &other, bool kind):k(1-other.k),vSign(-other.vSign){
        if(kind)k++;
    }
    pair<bool,long double> equate(constrains other){
        long double totVsign = vSign-other.vSign;
        long double totK = other.k - k;
        if(totVsign==0){
            return {0,totK==0};
        }
        totK/=totVsign;
        return {true,totK};
    }
    long double compute(long double x){
        return k+vSign*x;
    }
    void add(constrains &other){
        k+=other.k;
        vSign+=other.vSign;
    }
    void subtract(constrains &other){
        k-=other.k;
        vSign-=other.vSign;
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin >> N >> M;
    vector<vector<pair<int,bool>>> adj(N+1);
    for(int i=1;i<=M;i++){
        int u,v,c;
        cin >> u >> v >> c;
        adj[u].emplace_back(v,c==2);
        adj[v].emplace_back(u,c==2);
    }
    vector<bool> visited(N+1);
    vector<constrains> constrain(N+1);
    vector<long double> answer(N+1);
    bool works = true;
    for(int i=1;i<=N;i++)if(!visited[i]){
        vector<int> component;
        bool rootvaldecided = false;
        long double goodval = 0;
        auto dfs = [&](auto&& self,int x,constrains c)->void{
            if(visited[x]){
                auto [type,rootval] = c.equate(constrain[x]);
                if(type==0){
                    if(!rootval)works=false;
                } else {
                    if(!rootvaldecided)goodval=rootval;
                    rootvaldecided=true;
                    if(abs(goodval-rootval)>epsilon)works=false;
                }
                return;
            }
            visited[x]=true;
            constrain[x]=c;
            component.emplace_back(x);
            for(auto&[v,kind]:adj[x])self(self,v,{c,kind});
        };
        dfs(dfs,i,{});
        if(!works)break;
        if(!rootvaldecided){
            // decide a good value
            vector<pair<long double,constrains>> arr;
            constrains sum(0,0);
            for(int&j:component)if(constrain[j].vSign!=0){
                auto c = constrain[j];
                if(c.vSign<0){
                    c.vSign*=-1;
                    c.k*=-1;
                }
                auto [type,breakpoint] = c.equate({0,0});
                assert(type);
                arr.emplace_back(breakpoint,c);
                sum.subtract(c);
            }
            pair<long double,long double> answer = {sum.compute(-1e10),-1e10};
            sort(arr.begin(),arr.end(),[&](auto &a,auto &b){return a.first<b.first;});
            for(auto&[point,c]:arr){
                sum.add(c);
                sum.add(c);
                answer=min(answer,{sum.compute(point),point});
            }
            goodval=answer.second;
        }
        for(int&j:component)answer[j]=constrain[j].compute(goodval);
    }
    if(!works){
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for(int i=1;i<=N;i++){
        cout << answer[i] << ' ';
    }
    cout << '\n';
}

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