Graph Labelling SOLUTIONS GPHLBL

Graph Labelling SOLUTIONS GPHLBL

You are given a coordinated chart G with N vertices (numbered 1 through N) and M edges. We should signify the arrangement of its vertices by V, the arrangement of its edges by E and an edge from a vertex u to a vertex v by (u,v). At that point, how about we characterize: 
 
For each u,v∈V, R(u,v) is valid if v can be reached from u or bogus in any case. In particular, if u=v, it is in every case valid. 
 
For each v∈V, a lot of vertices N(v)={u∈V∣R(u,v)∧R(v,u)}. 
 
For every subset U⊆V, two arrangements of edges Out(U)={(u,v)∈E∣u∈U} and In(U)={(v,u)∈E∣u∈U}. 
 
You have to allocate a mark to each edge in E; you may just utilize names 1 and 2. The expenses of marking an edge are c1 and c2 for the names 1 and 2 separately. 
 
In the subsequent chart, Q limitations (numbered 1 through Q) should be fulfilled. For each substantial I, the I-th limitation is that the quantity of edges in a set Si with the name xi ought to be among li and ri (comprehensive); Si is controlled by a given vertex wi and the kind of this imperative ti as follows: 
 
ti=1: Si=Out(N(wi)) 
 
ti=2: Si=In(N(wi)) 
 
ti=3: Si=Out({wi}) 
 
ti=4: Si=In({wi}) 
 
Locate the littlest expense of naming all the edges so that these Q requirements are fulfilled or establish that there is no arrangement fulfilling all limitations. 
 
Info 
 
The main line of the info contains a solitary whole number T meaning the quantity of experiments. The portrayal of T experiments follows. 
 
The main line of each experiment contains three space-isolated whole numbers N, M and Q. 
 
Every one of the accompanying M lines contains two space-isolated whole numbers u and v meaning a coordinated edge (u,v). 
 
The following line contains two space-isolated whole numbers c1 and c2. 
 
Q lines follow. For each legitimate I, the I-th of these lines contains five space-isolated numbers ti, wi, xi, li and ri. 
 
Yield 
 
For each experiment, print a solitary line containing one whole number ― the littlest expense of marking the edges or −1 in the event that it is difficult to name the edges so that all requirements are fulfilled. 
 
Imperatives 
 
1≤T≤100 
 
1≤N≤3⋅104 
 
0≤M≤3⋅104 
 
0≤Q≤3⋅105 
 
1≤u,v≤N 
 
1≤c1,c2≤109 
 
1≤ti≤4 for each substantial I 
 
1≤wi≤N for each legitimate I 
 
xi∈{1,2} for each legitimate I 
 
0≤li≤ri≤M for each legitimate I 
 
the whole of N over all experiments doesn’t surpass 6⋅104 
 
the whole of M over all experiments doesn’t surpass 6⋅104 
 
the whole of Q over all experiments doesn’t surpass 6⋅105 
 
Model Input 
 
 
4 1 
 
1 2 
 
2 3 
 
1 3 
 
3 4 
 
10 20 
 
3 1 
 
Model Output 
 
50
 

 

Related:

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

1. Frog Sort Solution Codechef

2. Chef and Meetings Solution Codechef

3. Maximise Function Solution Codechef

4. Highest Divisor Solution Codechef

5. Cut the Cake Challenge Solution Codechef

6. Dream and the Multiverse Solution Codechef

7. Cell Shell Solution Codechef

8. Multiple Games Solution Codechef

9. Another Tree with Number Theory Solution Codechef

10. XOR Sums Solution Codechef

11. Prime Game Solution CodeChef

12. Team Name Solution Codechef

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

Leave a Comment