#include <bits/stdc++.h>
using namespace std;
int p[505];
int rt(int a){return p[a]==a?a:p[a]=rt(p[a]);}
int A[100005];
int B[100005];
int W[100005];
int n;
struct node{
int s,e;
vector<int> usefulmin,usefulmax;
node *l,*r;
node (int _s, int _e){
s = _s; e = _e;
if (s!=e){
l = new node(s,(s+e)/2);
r = new node((s+e)/2+1,e);
}
}
void construct(){
for (int x = 1; x<=n; x++){
p[x] = x;
}
for (int x = s; x<=e; x++){
if (rt(A[x])!=rt(B[x])){
usefulmin.push_back(x);
p[rt(A[x])] = rt(B[x]);
}
}
for (int x = 1; x<=n; x++){
p[x] = x;
}
for (int x = e; x>=s; x--){
if (rt(A[x])!=rt(B[x])){
usefulmax.push_back(x);
p[rt(A[x])] = rt(B[x]);
}
}
if (s==e) return;
l->construct();
r->construct();
}
void qu(vector<int> &low, vector<int> &high, int val){
//printf("qu %d-%d, %d, %d %d\n",s,e,val,W[s],W[e]);
if (W[s]>val){
for (auto x : usefulmin){
//printf("high add %d\n",x);
high.push_back(x);
}
return;
}
if (W[e]<=val){
for (auto x : usefulmax){
//printf("low add %d\n",x);
low.push_back(x);
}
return;
}
if (W[(s+e)/2]>=val){
l->qu(low,high,val);
r->qu(low,high,val);
}
else{
r->qu(low,high,val);
l->qu(low,high,val);
}
}
}*root;
main(){
scanf("%d",&n);
int m;
scanf("%d",&m);
vector<pair<int,pair<int,int>>> edgel;
for (int x = 0; x<m; x++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edgel.push_back({c,{a,b}});
}
sort(edgel.begin(),edgel.end());
for (int x = 0; x<m; x++){
A[x] = edgel[x].second.first;
B[x] = edgel[x].second.second;
W[x] = edgel[x].first;
}
root = new node(0,m-1);
root->construct();
int q;
scanf("%d",&q);
while (q--){
int v;
scanf("%d",&v);
vector<int> v1,v2;
root->qu(v1,v2,v);
//printf("qu fin\n");
int c1 = 0;
int c2 = 0;
long long ans = 0;
for (int x = 1; x<=n; x++) p[x] = x;
while (c1<v1.size() || c2<v2.size()){
//printf("%d %d\n",c1,c2);
if (c2==v2.size() || c1<v1.size() && v-W[v1[c1]]<W[v2[c2]]-v){
if (rt(A[v1[c1]])!=rt(B[v1[c1]])){
ans += v-W[v1[c1]];
p[rt(A[v1[c1]])] = rt(B[v1[c1]]);
}
c1++;
}
else{
if (rt(A[v2[c2]])!=rt(B[v2[c2]])){
ans += W[v2[c2]]-v;
p[rt(A[v2[c2]])] = rt(B[v2[c2]]);
}
c2++;
}
}
printf("%lld\n",ans);
}
}
Compilation message
reconstruction.cpp:73:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
73 | main(){
| ^~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | while (c1<v1.size() || c2<v2.size()){
| ~~^~~~~~~~~~
reconstruction.cpp:103:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | while (c1<v1.size() || c2<v2.size()){
| ~~^~~~~~~~~~
reconstruction.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | if (c2==v2.size() || c1<v1.size() && v-W[v1[c1]]<W[v2[c2]]-v){
| ~~^~~~~~~~~~~
reconstruction.cpp:105:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | if (c2==v2.size() || c1<v1.size() && v-W[v1[c1]]<W[v2[c2]]-v){
| ~~^~~~~~~~~~
reconstruction.cpp:105:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
105 | if (c2==v2.size() || c1<v1.size() && v-W[v1[c1]]<W[v2[c2]]-v){
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
reconstruction.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d",&m);
| ~~~~~^~~~~~~~~
reconstruction.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d%d",&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~
reconstruction.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
reconstruction.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%d",&v);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Execution timed out |
5074 ms |
38820 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
