結果

問題 No.3568 Range Restriction
コンテスト
ユーザー GOTKAKO
提出日時 2026-06-12 10:33:57
言語 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
結果
RE  
実行時間 -
コード長 1,868 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,754 ms
コンパイル使用メモリ 232,368 KB
実行使用メモリ 26,112 KB
最終ジャッジ日時 2026-06-12 10:34:10
合計ジャッジ時間 12,806 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 1 RE * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while(T--){
        int N,M; cin >> N >> M;
        vector<int> A(N);
        vector<tuple<int,int,int,int,int,int>> B(M);
        for(auto &[a,b,c,d,e,f] : B) cin >> a >> b >> c,a--,b--,c--,cin >> d >> e >> f;

        vector<int> time(M);
        vector<priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>>> Q(N);
        stack<int> st;
        int idx = 0;
        for(auto &[x,y,z,v,l,r] : B){
            if(v){
                Q.at(x).push({(v+1)/2,idx,0});
                Q.at(y).push({(v+1)/2,idx,0});
            }
            else st.push(idx);
            idx++;
        }
        while(st.size()){
            int pos = st.top(); st.pop();
            auto &[x,y,z,v,l,r] = B.at(pos);
            if(A.at(z) >= l) continue;
            A.at(z) = l;
            int a = A.at(z);
            while(Q.at(z).size()){
                auto [check,qpos,t] = Q.at(z).top();
                if(check > a) break;
                Q.at(z).pop();
                if(time.at(qpos) != t) continue;
                time.at(qpos)++;
                auto &[x2,y2,z2,v2,l2,r2] = B.at(qpos);
                if(A.at(x2)+A.at(y2) >= v) st.push(qpos);
                else{
                    int add = (v-A.at(x2)-A.at(y2)+1)/2;
                    Q.at(x2).push({A.at(x2)+add,qpos,time.at(qpos)});
                    Q.at(y2).push({A.at(y2)+add,qpos,time.at(qpos)});
                }
            }
        }

        bool ok = true;
        for(auto [x,y,z,v,l,r] : B){
            if(A.at(x)+A.at(y) < v) continue;
            assert(A.at(z) >= l);
            if(A.at(z) > r){ok = false; break;}
        }
        if(ok){for(auto a : A) cout << a << " "; cout << "\n";}
        else cout << "-1\n";
    }
}
0