#1168435 (C++23) No.3568 Range Restriction

• 問題: No.3568 Range Restriction
• ユーザー: sigma425
• 提出日時: 2026-06-06 02:11:02
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 221 ms / 2,000 ms
• コード長: 4,526 bytes
• コンパイル時間: 4,265 ms
• コンパイル使用メモリ: 348,752 KB
• 実行使用メモリ: 34,432 KB
• 最終ジャッジ日時: 2026-06-06 02:11:16
• 合計ジャッジ時間: 12,967 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 21

ソースコード

// #line 1 "3568.cpp"
// #pragma GCC target("avx2,avx512f,avx512vl,avx512bw,avx512dq,avx512cd,avx512vbmi,avx512vbmi2,avx512vpopcntdq,avx512bitalg,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("Ofast")

// #line 2 "/home/sigma/comp/library/template.hpp"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> bool chmax(T& x, U y){
	if(x<y){ x=y; return true; }
	return false;
}
template<class T,class U> bool chmin(T& x, U y){
	if(y<x){ x=y; return true; }
	return false;
}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();}
template<class T>
V<T> Vec(size_t a) {
	return V<T>(a);
}
template<class T, class... Ts>
auto Vec(size_t a, Ts... ts) {
  return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...));
}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}

template<typename Tuple, size_t... Is>
void print_tuple_impl(ostream& os, const Tuple& tup, index_sequence<Is...>){
	((os << (Is == 0 ? "" : ",") << get<Is>(tup)), ...);
}
template<typename... Args>
std::ostream& operator<<(std::ostream& os, const std::tuple<Args...>& tup) {
	os << "(";
	print_tuple_impl(os, tup, std::index_sequence_for<Args...>{});
	os << ")";
	return os;
}

template<class T> istream& operator>>(istream& i, V<T> &vc){
	for(T& v: vc) i >> v;
	return i;
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
template<class T> ostream& operator<<(ostream& o,const deque<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
const bool DEBUG = true;
const bool SUBMIT = false;
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) do{cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__);}while(0)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
const bool DEBUG = false;
const bool SUBMIT = true;
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif

template<class D> D divFloor(D a, D b){
	return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}
template<class D> D divCeil(D a, D b) {
	return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}
// #line 5 "3568.cpp"

struct Query{
	int x,y,z;
	ll v,l,r;
};

void solve(){
	int N,M; cin >> N >> M;
	V<Query> qs(M);
	rep(i,M){
		int x,y,z,v,l,r; cin >> x >> y >> z >> v >> l >> r;
		x--,y--,z--;
		qs[i] = {x,y,z,v,l,r};
	}
	V<ll> A(N);
	queue<int> q;
	V<bool> in_q(M);
	using PQ = priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>;	// val,id
	V<PQ> pq(N);
	auto Push = [&](int i){
		if(in_q[i]) return;
		in_q[i] = true;
		q.push(i);
	};
	rep(i,M){
		if(qs[i].v == 0) Push(i);
		else{
			ll hey = (qs[i].v+1)/2;
			pq[qs[i].x].push({hey, i});
			pq[qs[i].y].push({hey, i});
		}
	}
	while(!q.empty()){
		int i = q.front(); q.pop();
		auto [x,y,z,v,l,r] = qs[i];
		if(A[z] < l){
			A[z] = l;
			while(!pq[z].empty() && pq[z].top().first <= A[z]){
				int j = pq[z].top().second; pq[z].pop();
				if(A[qs[j].x] + A[qs[j].y] >= qs[j].v){
					Push(j);
				}else{
					ll hey = (qs[j].v - A[qs[j].x] - A[qs[j].y] + 1) / 2;
					pq[qs[j].x].push({A[qs[j].x] + hey, j});
					pq[qs[j].y].push({A[qs[j].y] + hey, j});
				}
			}
		}
	}
	rep(i,M){
		auto [x,y,z,v,l,r] = qs[i];
		if(A[x]+A[y] >= v && !(l <= A[z] && A[z] <= r)){
			cout << -1 << '\n';
			return;
		}
	}
	rep(i,N) cout << A[i] << ' ';
	cout << '\n';
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	int T; cin >> T;
	while(T--) solve();
}