結果

問題 No.3465 Lis! Lis! Lis!
コンテスト
ユーザー jupiter_68
提出日時 2026-02-28 16:03:04
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 5,498 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,530 ms
コンパイル使用メモリ 231,048 KB
実行使用メモリ 26,952 KB
最終ジャッジ日時 2026-02-28 16:03:39
合計ジャッジ時間 30,072 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define reps(i, l, r) for(ll i = (l); i < (r); ++i)
#define rrep(i, l, r) for(ll i = (r)-1; i >= (l); --i)
#define sz(x) (ll) (x).size()
template <typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template <typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }

struct Edge {
    ll from, to, cost;
    Edge (ll from, ll to, ll cost = 1ll) : from(from), to(to), cost(cost) {}
};
struct Graph {
    vector<vector<Edge>> G;
    Graph() = default;
    explicit Graph(ll N) : G(N) {}
    size_t size() const {
        return G.size();
    }
    void add(ll from, ll to, ll cost = 1ll, bool direct = 0) {
        G[from].emplace_back(from, to, cost);
        if (!direct) G[to].emplace_back(to, from, cost);
    }
    vector<Edge> &operator[](const int &k) {
        return G[k];
    }
};
using Edges = vector<Edge>;

const ll mod = 998244353; // 1000000007;

struct mint {
    ll x;
    mint(ll y = 0) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    mint &operator+=(const mint &p) {
        if ((x += p.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator-=(const mint &p) {
        if ((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator*=(const mint &p) {
        x = (ll)(1ll * x * p.x % mod);
        return *this;
    }
    mint &operator/=(const mint &p) {
        *this *= p.inv();
        return *this;
    }
    mint operator-() const { return mint(-x); }
    mint operator+(const mint &p) const { return mint(*this) += p; }
    mint operator-(const mint &p) const { return mint(*this) -= p; }
    mint operator*(const mint &p) const { return mint(*this) *= p; }
    mint operator/(const mint &p) const { return mint(*this) /= p; }
    bool operator==(const mint &p) const { return x == p.x; }
    bool operator!=(const mint &p) const { return x != p.x; }
    friend ostream &operator<<(ostream &os, const mint &p) { return os << p.x; }
    friend istream &operator>>(istream &is, mint &a) {
        ll t; is >> t; a = mint(t); return (is);
    }
    mint inv() const { return pow(mod - 2); }
    mint pow(ll n) const {
        mint ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
};

template <class Type = ll>
struct WeightedUnionFind {
	vl par; vec<Type> wd;
	WeightedUnionFind() = default;
	explicit WeightedUnionFind(size_t n)
    : par(n, -1), wd(n) {}
	ll find(int i) {
		if (par[i] < 0) return i;
		const ll root = find(par[i]);
		wd[i] += wd[par[i]];
		return (par[i] = root);
	}
	void merge(int a, int b, Type w) {
		w += weight(a), w -= weight(b);
		a = find(a), b = find(b);
		if (a == b) return;
		if (-par[a] < -par[b]) { swap(a, b); w = -w; }
		par[a] += par[b];
		par[b] = a;
		wd[b] = w;
	}
	Type diff(int a, int b) {
		return (weight(b) - weight(a));
	}
	bool same(int a, int b) {
		return (find(a) == find(b));
	}
	int size(int i) {
		return -par[find(i)];
	}
	Type weight(int i) {
		find(i);
		return wd[i];
	}
};

void solve(){
    auto tim = clock();
    ll N, M; cin >> N >> M;
    vl l(M), r(M), w(M);
    vv<pll> G(N);
    rep(i, M){
        cin >> l[i] >> r[i] >> w[i];
        l[i]--; r[i]--; w[i]--;
        G[l[i]].push_back({r[i], w[i]});
        G[r[i]].push_back({l[i], -w[i]});
    }
    vec<pll> dp(N, {0, 4e18});
    auto merge = [&](pll& a, pll b)->bool{
        a = pll{max(a.first, b.first), min(a.second, b.second)};
        return (a.first > a.second);
    };
    dp[0] = {1, 1};
    deque<ll> Q; Q.push_back(0);
    vl vis(N, 0); vis[0] = 1;
    while(!Q.empty()){
        ll p = Q.front(); Q.pop_front();
        for(pll e : G[p]){
            ll nx = e.first, vl = e.second;
            pll pr = dp[p]; pr.first += vl, pr.second += vl;
            if(merge(dp[nx], pr)){
                cout << "No" << endl;
                return;
            }
            if(!vis[nx]){
                Q.push_front(nx); vis[nx] = 1;
            }
        }
        if(p + 1 < N){
            pll pr = dp[p]; pr.second++;
            if(merge(dp[p+1], pr)){
                cout << "No" << endl;
                return;
            }
            if(!vis[p+1]) Q.push_back(p+1), vis[p+1] = 1;
        }
        if(p > 0){
            pll pr = dp[p]; pr.first--;
            if(merge(dp[p-1], pr)){
                cout << "No" << endl;
                return;
            }
            if(!vis[p-1]) Q.push_back(p-1), vis[p-1] = 1;
        }
    }
    while(clock() - tim < CLOCKS_PER_SEC * 16 / 10){
        rep(i, N-1){
            {
                pll pr = dp[i]; pr.second++; merge(dp[i+1], pr);
            }
            {
                pll pr = dp[i+1]; pr.first--; merge(dp[i], pr);
            }
        }
    }
    cout << "Yes" << endl;
    rep(i, N){
        cout << dp[i].first << " \n"[i == N-1];
    }
    return;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}
0