#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
const llo mod=1e9+7;
int n,m;
vector<pair<int,int>> adj[501];
vector<pair<int,pair<int,int>>> ee;
int ac=-1;
int cc=-1;
void dfs(int no,int par=-1,int ma=-1){
if(ac==no){
cc=ma;
}
for(auto j:adj[no]){
if(j.a!=par){
dfs(j.a,no,max(ma,j.b));
}
}
}
int re[100001];
void solve(){
for(int i=0;i<n;i++){
adj[i].clear();
}
for(int i=ee.size()-1;i>=0;i--){
ac=ee[i].b.b;
cc=-1;
dfs(ee[i].b.a);
if(cc==-1){
adj[ac].pb({ee[i].b.a,i});
adj[ee[i].b.a].pb({ac,i});
re[i]=m;
}
else{
// cout<<22<<endl;
vector<pair<int,int>> ee2;
for(int j=0;j<n;j++){
for(auto jj:adj[j]){
if(jj.b==cc){
continue;
}
ee2.pb(jj);
}
adj[j]=ee2;
ee2.clear();
}
adj[ac].pb({ee[i].b.a,i});
adj[ee[i].b.a].pb({ac,i});
re[i]=cc;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for(int i=0;i<m;i++){
int aa,bb,cc;
cin>>aa>>bb>>cc;
aa--;
bb--;
ee.pb({cc,{aa,bb}});
}
sort(ee.begin(),ee.end());
solve();
vector<pair<pair<int,int>,int>> qq;
for(int i=0;i<m;i++){
//if query>(x+y)/2
if(re[i]<m){
qq.pb({{(ee[i].a+ee[re[i]].a)/2,10},i});
}
}
/*for(auto j:ee){
cout<<j.a<<":"<<j.b.a<<":"<<j.b.b<<endl;
}
for(int i=0;i<ee.size();i++){
cout<<re[i]<<",";
}
cout<<endl;*/
//return 0;
reverse(ee.begin(),ee.end());
solve();
/* for(int i=0;i<ee.size();i++){
cout<<re[i]<<",";
}
cout<<endl;*/
//return 0;
for(int i=0;i<m;i++){
//if query>(x+y)/2
if(re[i]<m){
qq.pb({{(ee[i].a+ee[re[i]].a+2)/2,-10},m-i-1});
}
else{
qq.pb({{-10,-10},m-i-1});
}
}
reverse(ee.begin(),ee.end());
multiset<int> cur;
int q;
cin>>q;
for(int ii=0;ii<q;ii++){
int aa;
cin>>aa;
qq.pb({{aa,0},ii});
}
sort(qq.begin(),qq.end());
for(auto j:qq){
if(j.a.b==0){
llo ans=0;
for(auto jj:cur){
ans+=abs(j.a.a-jj);
}
cout<<ans<<endl;
}
else if(j.a.b==-10){
cur.insert(ee[j.b].a);
}
else if(j.a.b==10){
auto jj=cur.find(ee[j.b].a);
assert(jj!=cur.end());
/* if(jj==cur.end()){
cout<<-1<<endl;
continue;
}*/
cur.erase(jj);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Execution timed out |
5064 ms |
26768 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 18 |
Halted |
0 ms |
0 KB |
- |
