| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1211356 | walizamanee | 저울 (IOI15_scales) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int t , n , q , shesh[300001] , one , two , three , par[300001] , me , him , ans;
long long b[300001] , col[300001] , chotocol[300001] , ek , dui;
vector<vector<int>> arr;
set<int> baki[300001];
void comb( int mi , int hi ) {
me = par[mi];
him = par[hi];
if( me != him ) {
if( baki[me].size() < baki[him].size() ) swap( me , him );
chotocol[me] = min( chotocol[me] , chotocol[him] );
for( auto it = baki[him].begin(); it != baki[him].end(); ++it ) {
baki[me].insert(*it);
par[*it] = me;
}
baki[him].clear();
}
}
int main() {
cin >> t;
while(t--){
cin >> n >> q;
ans = 0;
arr.clear();
for( int z = 1; z <= n; z++ ) {
cin >> b[z];
shesh[z] = -1;
par[z] = z;
chotocol[z] = (ll)1e10;
baki[z].clear();
baki[z].insert(z);
}
for( int z = 0; z < q; z++ ) {
cin >> one >> two >> three;
arr.push_back({one , two , three});
shesh[three] = z;
}
for( int z = 1; z <= n; z++ ) {
if( shesh[z] == -1 ) {
baki[z].clear();
col[z] = b[z];
chotocol[z] = b[z];
}
}
for( int z = 0; z < q; z++ ) {
if( shesh[arr[z][2]] == z ) {
comb( arr[z][0] , arr[z][1] );
comb( arr[z][0] , arr[z][2] );
one = par[arr[z][0]];
//cout << one << " " << chotocol[one] << "\n";
if( chotocol[one] < b[arr[z][2]] ) ans = -1;
else{
//cout << "lol" << b[arr[z][2]] << "\n";
if( baki[one].size() == 0 ) {
if( chotocol[one] != b[arr[z][2]] ) ans = -1;
}
else{
for( auto it = baki[one].begin(); it != baki[one].end(); ++it ) {
col[*it] = b[arr[z][2]];
}
baki[one].clear();
chotocol[one] = b[arr[z][2]];
}
}
}
else{
comb( arr[z][0] , arr[z][1] );
comb( arr[z][0] , arr[z][2] );
}
}
for( int z = 1; z <= n; z++ ) {
if( baki[z].size() != 0 ) {
for( auto it = baki[z].begin(); it != baki[z].end(); ++it ) {
col[*it] = chotocol[z];
}
baki[z].clear();
}
}
if( ans == -1 ) cout << -1 ;
else for( int z = 1; z <= n; z++ ) cout << col[z] << " ";
cout << "\n";
}
return 0;
}