Submission #1204631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204631		Unforgettablepl	Graph (BOI20_graph)	C++20	0 / 100	0 ms	328 KiB

Graph

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

#define int long long

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

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<int> answer(N+1);
    bool works = true;
    for(int i=1;i<=N;i++)if(!visited[i]){
        vector<int> component;
        bool rootvaldecided = false;
        int 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;
                    if(goodval!=rootval)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;
        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++){
        if(answer[i]<0)cout<<'-';
        cout << abs(answer[i])/2ll;
        if(abs(answer[i])&1)cout<<".5";
        cout << ' ';
    }
    cout << '\n';
}

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