Submission #1235696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235696		gry3125	Graph (BOI20_graph)	C++20	0 / 100	0 ms	320 KiB

Graph

#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
using namespace std;

int n, m; bool okk = 0;
vector<pair<pair<int,int>,int>> e;
vector<ll> a, memo;

void dp(int i) {
    if (i == n) {
        bool ok = 1;
        for (auto x : e) {
            int aa = x.fi.fi, bb = x.fi.se, c = x.se;
            if (c == 1 && a[aa] + a[bb] != 2) ok = 0;
            if (c == 2 && a[aa] + a[bb] != 4) ok = 0;
        }
        if (ok) {
            okk = 1;
            for (int i = 0; i < n; i++) memo[i] = a[i];
        }
        return;
    }
    a[i] = 0; dp(i+1);
    a[i] = 1; dp(i+1);
    a[i] = 2; dp(i+1);
    a[i] = 3; dp(i+1);
    a[i] = 4; dp(i+1);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c; 
        cin >> a >> b >> c;
        e.pb({{a-1, b-1}, c});
    }
    a.resize(n); memo.resize(n);
    dp(0);
    if (!okk) {cout << "NO"; return 0;}
    cout << "YES\n";
    for (int i = 0; i < n; i++) {
        if (memo[i] == 0) cout << 0 << " ";
        if (memo[i] == 1) cout << 0.5 << " ";
        if (memo[i] == 2) cout << 1 << " ";
        if (memo[i] == 3) cout << 1.5 << " ";
        if (memo[i] == 4) cout << 2 << " ";
    }
    return 0;
}

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