제출 #1368522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368522		dashka	Graph (BOI20_graph)	C++20	100 / 100	53 ms	11664 KiB

Graph

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int N, M;
vector<pair<int,int>> adj[100005]; // (хөрш, өнгө)
ll alphaV[100005];
int betaV[100005];
bool visited[100005];
 
int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    
    vector<ll> result(N+1);
    bool possible = true;
    
    for (int start = 1; start <= N && possible; start++) {
        if (visited[start]) continue;
        
        vector<int> comp;
        queue<int> q;
        q.push(start);
        visited[start] = true;
        alphaV[start] = 0;
        betaV[start] = 1;
        
        ll r = 0;
        bool fixed = false;
        bool ok = true;
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            comp.push_back(u);
            for (auto [v, c] : adj[u]) {
                ll target = 2 * c;
                ll new_a = target - alphaV[u];
                int new_b = -betaV[u];
                
                if (!visited[v]) {
                    visited[v] = true;
                    alphaV[v] = new_a;
                    betaV[v] = new_b;
                    q.push(v);
                } else {
                    if (betaV[v] == new_b) {
                        if (alphaV[v] != new_a) { ok = false; break; }
                    } else {
                        ll diff = new_a - alphaV[v];
                        ll denom = betaV[v] - new_b;
                        if (diff % denom != 0) { ok = false; break; }
                        ll r_new = diff / denom;
                        if (fixed && r != r_new) { ok = false; break; }
                        r = r_new;
                        fixed = true;
                    }
                }
            }
            if (!ok) break;
        }
        
        if (!ok) { possible = false; break; }
        
        if (!fixed) {
            vector<ll> t;
            for (int i : comp)
                t.push_back(-(ll)betaV[i] * alphaV[i]);
            sort(t.begin(), t.end());
            r = t[t.size() / 2];
        }
        
        for (int i : comp)
            result[i] = alphaV[i] + (ll)betaV[i] * r;
    }
    
    if (!possible) {
        printf("NO\n");
    } else {
        printf("YES\n");
        for (int i = 1; i <= N; i++) {
            ll u = result[i];
            char sep = (i == N) ? '\n' : ' ';
            if (u % 2 == 0) printf("%lld%c", u/2, sep);
            else if (u < 0)
                printf("-%lld.5%c", (-u)/2, sep);
            else
                printf("%lld.5%c", u/2, sep);
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Graph.cpp: In function 'int main()':
Graph.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Graph.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 12 / 12
• 서브태스크 2: 17 / 17
• 서브태스크 3: 24 / 24
• 서브태스크 4: 42 / 42
• 서브태스크 5: 5 / 5