#include<bits/stdc++.h>
#pragma GCC optimize("trapv")
#define st first
#define nd second
#define pb(x) push_back(x)
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
using namespace std;
///~~~~~~~~~~~~~~~~~~~~~~~~~~
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
///~~~~~~~~~~~~~~~~~~~~~~~~~
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=1e5+5, INF=1e9+5, mod=1e9+7;
vector<pair<int, pii> > edg;
int r[N], siz[N];
vector<pair<pii, pair<pii, int> > > Q;
vector<pii> upd;
vector<bool> ans;
int find(int v){
if(r[v]==v)return v;
return find(r[v]);
}
void Union(int a, int b){
a=find(a);
b=find(b);
if(a==b){
upd.pb(mp(0, 0));
return;
}
if(siz[a]>siz[b])swap(a, b);
r[a]=b;
siz[b]+=siz[a];
upd.pb(mp(a, b));
}
void Union2(int a, int b){
r[a]=a;
siz[b]-=siz[a];
upd.pp();
}
int L1[N], R1[N], L2[N], R2[N];//[L1, R1] - pierwszy na prawo, ktory moze byc zamiast tej kraw
int K=200;
void solve(){
sort(Q.begin(), Q.end(), [](pair<pii, pair<pii, int> > a, pair<pii, pair<pii, int> > b){
if(a.st.st/K!=b.st.st/K)return a.st.st<b.st.st;
return a.st.nd<b.st.nd;
});
int a=K;
int b=a;
vector<pair<pii, pair<pii, int> > > Q2;
for(int i=0; i<Q.size(); i++){
if(i && Q[i].st.st/K!=Q[i-1].st.st/K){
while(upd.size())Union2(upd.back().st, upd.back().nd);
//for(int j=1; j<=4; j++)assert(r[j]==j && siz[j]==1);
a=K*(Q[i].st.st/K+1);
b=a;
}
//cout<<upd.size();
if(b-1>Q[i].st.nd){
Q2.pb(Q[i]);
continue;
}
while(b<=Q[i].st.nd){
Union(edg[b].nd.st, edg[b].nd.nd);
b++;
}
for(int j=a-1; j>=Q[i].st.st; j--){
Union(edg[j].nd.st,edg[j].nd.nd);
}
ans[Q[i].nd.nd]=(find(Q[i].nd.st.st)==find(Q[i].nd.st.nd));
//cout<<upd.size();
for(int j=Q[i].st.st; j<a; j++){
Union2(upd.back().st, upd.back().nd);
}
}
while(upd.size())Union2(upd.back().st, upd.back().nd);
for(auto i:Q2){
for(int j=i.st.st; j<=i.st.nd; j++){
Union(edg[j].nd.st, edg[j].nd.nd);
}
ans[i.nd.nd]=(find(i.nd.st.st)==find(i.nd.st.nd));
for(int j=i.st.nd; j>=i.st.st; j--){
Union2(upd.back().st, upd.back().nd);
}
}
}
void rec(){
Q.clear();
for(int i=0; i<edg.size(); i++){
int m=(L1[i]+R1[i]+1)/2;
if(R1[i]==-1)m=-1;
if(m!=-1)Q.pb(mp(mp(m, i-1), mp(edg[i].nd, 2*i)));
m=(L2[i]+R2[i])/2;
if(m!=edg.size())Q.pb(mp(mp(i+1, m), mp(edg[i].nd, 2*i+1)));
}
solve();
for(int i=0; i<edg.size(); i++){
int m=(L1[i]+R1[i]+1)/2;
if(R1[i]==-1)m=-1;
if(m!=-1){
if(ans[2*i])L1[i]=m;
else R1[i]=m-1;
}
m=(L2[i]+R2[i])/2;
if(m!=edg.size()){
if(ans[2*i+1])R2[i]=m;
else L2[i]=m+1;
}
}
}
int main(){
BOOST;
int n, m;
cin>>n>>m;
edg.rsz(m);
for(auto &i:edg)cin>>i.nd.st>>i.nd.nd>>i.st;
sor(edg);
for(int i=1; i<=n; i++)siz[i]=1, r[i]=i;
ans.rsz(2*m);
for(int i=0; i<m; i++){
L1[i]=-1;
R1[i]=i-1;
L2[i]=i+1;
R2[i]=m;
}
for(int i=0; i<20; i++)rec();
/*for(int i=0; i<m; i++){
cout<<edg[i].nd.st<<" "<<edg[i].nd.nd<<" "<<edg[i].st<<"\n";
cout<<L1[i]<<" "<<R1[i]<<" "<<L2[i]<<" "<<R2[i]<<"\n";
}*/
/*Q.clear();
Q.push_back(mp(mp(0, -1), mp(mp(1 , 2), 0)));
solve();
cout<<ans[0];*/
vector<pair<int, pii>> V;
for(int i=0; i<m; i++){
if(L1[i]!=-1)V.pb(mp(edg[L1[i]].st+edg[i].st, mp(1, edg[i].st)));
else V.pb(mp(-2*INF, mp(1, edg[i].st)));
V.pb(mp(2*edg[i].st, mp(-2, edg[i].st)));
if(L2[i]!=m)V.pb(mp(edg[L2[i]].st+edg[i].st, mp(1, edg[i].st)));
}
sort(all(V));
long long sum=0;
int q;
cin>>q;
vector<pii> Q(q);
for(int i=0; i<q; i++){
cin>>Q[i].st;
Q[i].st*=2;
Q[i].nd=i;
}
sort(Q.begin(), Q.end());
vector<ll> ans(q);
int ile=0, wsk=0;
for(int i=0; i<V.size(); i++){
while(wsk<q && Q[wsk].st<=V[i].st){
ans[Q[wsk].nd]=sum-ile*1ll*(Q[wsk].st/2);
wsk++;
}
ile+=V[i].nd.st;
sum+=V[i].nd.st*1ll*V[i].nd.nd;
}
while(wsk<q){
ans[Q[wsk].nd]=sum-ile*1ll*(Q[wsk].st/2);
wsk++;
}
for(int i:ans){
cout<<i<<"\n";
}
}
Compilation message
reconstruction.cpp: In function 'void solve()':
reconstruction.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<std::pair<int, int>, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i=0; i<Q.size(); i++){
| ~^~~~~~~~~
reconstruction.cpp: In function 'void rec()':
reconstruction.cpp:114:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i=0; i<edg.size(); i++){
| ~^~~~~~~~~~~
reconstruction.cpp:119:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | if(m!=edg.size())Q.pb(mp(mp(i+1, m), mp(edg[i].nd, 2*i+1)));
| ~^~~~~~~~~~~~
reconstruction.cpp:122:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int i=0; i<edg.size(); i++){
| ~^~~~~~~~~~~
reconstruction.cpp:130:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | if(m!=edg.size()){
| ~^~~~~~~~~~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:180:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Execution timed out |
5048 ms |
8276 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
