#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back
using namespace std;
const int N = 100005;
int n, m;
pair < int, pair < int, int > > P[N];
vector < int > g[505];
void del (int x, int y){
for (int i = 0; i < g[x].size(); i++){
if (g[x][i] == y){
swap (g[x][i], g[x].back());
g[x].pop_back();
break;
}
}
}
int G[505][505];
int par[505];
void dfs (int k, int p){
par[k] = p;
for (int to : g[k])
if (to != p)
dfs (to, k);
}
int st[505], en[505];
int q;
int X[N*10], ans[N*10], C[N*10];
main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for (int u,v,x,i = 1; i <= m; i++){
cin >> u >> v >> x;
P[i] = {x, {u, v}};
}
sort (P+1, P+m+1);
for (int u,v,i = 1; i <= m; i++){
u = P[i].S.F;
v = P[i].S.S;
dfs (u, 0);
if (par[v] == 0){
g[u].pb (v);
g[v].pb (u);
st[i] = 0;
G[u][v] = G[v][u] = P[i].F;
}
else {
int x = P[i].F+1;
int node = v, c = 0;
while (node != u){
if (G[node][par[node]] < x){
x = G[node][par[node]];
c = node;
}
node = par[node];
}
del (c, par[c]);
del (par[c], c);
g[u].pb (v);
g[v].pb (u);
G[u][v] = G[v][u] = P[i].F;
st[i] = (P[i].F + G[c][par[c]] + 2) / 2;
}
for (int j = 1; j <= n; j++)
par[j] = 0;
}
for (int i = 1; i <= n; i++)
g[i].clear();
for (int u,v, i = m; i >= 1; i--){
u = P[i].S.F;
v = P[i].S.S;
dfs (u, 0);
if (par[v] == 0){
g[u].pb (v);
g[v].pb (u);
en[i] = 1e9;
}
else {
int x = P[i].F-1;
int node = v, c = 0;
while (node != u){
if (G[node][par[node]] > x){
x = G[node][par[node]];
c = node;
}
node = par[node];
}
del (c, par[c]);
del (par[c], c);
g[u].pb (v);
g[v].pb (u);
G[u][v] = G[v][u] = P[i].F;
en[i] = (P[i].F + G[c][par[c]]) / 2;
}
for (int j = 1; j <= n; j++)
par[j] = 0;
}
cin >> q;
for (int i = 1; i <= q; i++){
cin >> X[i];
}
for (int i = 1; i <= m; i++){
int a1, b1;
int l = 1, r = q+1;
while (l < r){
int mid = l + r >> 1;
if (X[mid] < st[i])
l = mid + 1;
else
r = mid;
}
a1 = l;
l = 0, r = q;
while (l < r){
int mid = l + r + 1 >> 1;
if (X[mid] > P[i].F)
r = mid - 1;
else
l = mid;
}
b1 = l;
C[a1]--;
C[b1+1]++;
ans[a1] += P[i].F;
ans[b1+1] -= P[i].F;
a1 = b1 + 1;
l = 0, r = q;
while (l < r){
int mid = l + r + 1 >> 1;
if (X[mid] > en[i])
r = mid - 1;
else
l = mid;
}
b1 = l;
C[a1]++;
C[b1+1]--;
ans[a1] -= P[i].F;
ans[b1+1] += P[i].F;
}
for (int i = 1; i <= q; i++){
ans[i] += ans[i-1];
C[i] += C[i-1];
cout << abs(X[i] * C[i] + ans[i]) << endl;
}
}
Compilation message
reconstruction.cpp: In function 'void del(long long int, long long int)':
reconstruction.cpp:16:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for (int i = 0; i < g[x].size(); i++){
| ~~^~~~~~~~~~~~~
reconstruction.cpp: At global scope:
reconstruction.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
40 | main() {
| ^~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:117:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
117 | int mid = l + r >> 1;
| ~~^~~
reconstruction.cpp:126:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
126 | int mid = l + r + 1 >> 1;
| ~~~~~~^~~
reconstruction.cpp:141:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
141 | int mid = l + r + 1 >> 1;
| ~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
