| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 556667 | 2022-05-03T13:55:17 Z | 600Mihnea | Reconstruction Project (JOI22_reconstruction) | C++17 | 32 ms | 4668 KB |
#include <bits/stdc++.h>
bool home = 1;
using namespace std;
typedef long long ll;
struct Edge{
int a;
int b;
int w;
};
bool operator < (Edge a,Edge b) {
return a.w<b.w;
}
const int N=500+7;
const int M=100000+7;
const int Q=1000000+7;
const int INF=(int)1e9+7;
int n;
int m;
int q;
int t[N];
Edge edges[M];
void clr() {
for(int i=1;i<=n;i++) t[i]=i;
}
int root(int a) {
if (t[a]==a) return a;
return t[a]=root(t[a]);
}
void join(int a,int b) {
t[root(a)]=root(b);
}
int smallest[N];
int biggest[N];
signed main() {
#ifdef ONLINE_JUDGE
home = 0;
#endif
home=0;
if (home) {
freopen("I_am_iron_man", "r", stdin);
}
else {
ios::sync_with_stdio(0); cin.tie(0);
}
cin>>n>>m;
for (int i=1;i<=m;i++) {
cin>>edges[i].a>>edges[i].b>>edges[i].w;
smallest[i]=-INF;
biggest[i]=+INF;
}
sort(edges+1,edges+m+1);
for (int i=2;i<=m;i++){
assert(edges[i-1].w<=edges[i].w);
}
for (int i=1;i<=m;i++) {
clr();
int low=i-1;
while (low>=1&&root(edges[i].a)!=root(edges[i].b)) {
join(edges[low].a,edges[low].b);
low--;
}
if(root(edges[i].a)==root(edges[i].b)) low++;
clr();
int high=i+1;
while(high<=m&&root(edges[i].a)!=root(edges[i].b)) {
join(edges[high].a,edges[high].b);
high++;
}
if(root(edges[i].a)==root(edges[i].b)) high--;
if (low>=1) smallest[i]=(edges[low].w+edges[i].w+1)/2;
if (high<=m) biggest[i]=(edges[high].w+edges[i].w-1)/2;
}
cin>>q;
for (int iq=1;iq<=q;iq++) {
int w;
cin>>w;
ll sol=0;
for(int i=1;i<=m;i++) {
if (smallest[i]<=w&&w<=biggest[i]) {
sol+=abs(edges[i].w-w);
}
}
cout<<sol<<"\n";
}
}
/**
1 : -1 4
2 : -1 5
3 : 4 7
4 : -1 11
5 : 5 9
6 : -1 10
7 : 7 1000000001
8 : 9 1000000001
9 : 10 1000000001
10 : 11 1000000001
**/
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 212 KB | Output is correct |
| 2 | Correct | 1 ms | 212 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 336 KB | Output is correct |
| 5 | Correct | 0 ms | 212 KB | Output is correct |
| 6 | Correct | 1 ms | 212 KB | Output is correct |
| 7 | Correct | 0 ms | 212 KB | Output is correct |
| 8 | Correct | 1 ms | 296 KB | Output is correct |
| 9 | Correct | 1 ms | 212 KB | Output is correct |
| 10 | Correct | 1 ms | 212 KB | Output is correct |
| 11 | Correct | 1 ms | 212 KB | Output is correct |
| 12 | Correct | 1 ms | 340 KB | Output is correct |
| 13 | Correct | 1 ms | 336 KB | Output is correct |
| 14 | Correct | 1 ms | 340 KB | Output is correct |
| 15 | Correct | 0 ms | 212 KB | Output is correct |
| 16 | Correct | 1 ms | 212 KB | Output is correct |
| 17 | Correct | 1 ms | 340 KB | Output is correct |
| 18 | Correct | 1 ms | 340 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 212 KB | Output is correct |
| 2 | Correct | 1 ms | 212 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 336 KB | Output is correct |
| 5 | Correct | 0 ms | 212 KB | Output is correct |
| 6 | Correct | 1 ms | 212 KB | Output is correct |
| 7 | Correct | 0 ms | 212 KB | Output is correct |
| 8 | Correct | 1 ms | 296 KB | Output is correct |
| 9 | Correct | 1 ms | 212 KB | Output is correct |
| 10 | Correct | 1 ms | 212 KB | Output is correct |
| 11 | Correct | 1 ms | 212 KB | Output is correct |
| 12 | Correct | 1 ms | 340 KB | Output is correct |
| 13 | Correct | 1 ms | 336 KB | Output is correct |
| 14 | Correct | 1 ms | 340 KB | Output is correct |
| 15 | Correct | 0 ms | 212 KB | Output is correct |
| 16 | Correct | 1 ms | 212 KB | Output is correct |
| 17 | Correct | 1 ms | 340 KB | Output is correct |
| 18 | Correct | 1 ms | 340 KB | Output is correct |
| 19 | Correct | 1 ms | 212 KB | Output is correct |
| 20 | Runtime error | 32 ms | 4428 KB | Execution killed with signal 11 |
| 21 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 328 KB | Output is correct |
| 2 | Correct | 1 ms | 212 KB | Output is correct |
| 3 | Correct | 1 ms | 212 KB | Output is correct |
| 4 | Runtime error | 32 ms | 4668 KB | Execution killed with signal 11 |
| 5 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 212 KB | Output is correct |
| 2 | Correct | 1 ms | 212 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 336 KB | Output is correct |
| 5 | Correct | 0 ms | 212 KB | Output is correct |
| 6 | Correct | 1 ms | 212 KB | Output is correct |
| 7 | Correct | 0 ms | 212 KB | Output is correct |
| 8 | Correct | 1 ms | 296 KB | Output is correct |
| 9 | Correct | 1 ms | 212 KB | Output is correct |
| 10 | Correct | 1 ms | 212 KB | Output is correct |
| 11 | Correct | 1 ms | 212 KB | Output is correct |
| 12 | Correct | 1 ms | 340 KB | Output is correct |
| 13 | Correct | 1 ms | 336 KB | Output is correct |
| 14 | Correct | 1 ms | 340 KB | Output is correct |
| 15 | Correct | 0 ms | 212 KB | Output is correct |
| 16 | Correct | 1 ms | 212 KB | Output is correct |
| 17 | Correct | 1 ms | 340 KB | Output is correct |
| 18 | Correct | 1 ms | 340 KB | Output is correct |
| 19 | Correct | 1 ms | 212 KB | Output is correct |
| 20 | Runtime error | 1 ms | 576 KB | Execution killed with signal 11 |
| 21 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 212 KB | Output is correct |
| 2 | Correct | 1 ms | 212 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 336 KB | Output is correct |
| 5 | Correct | 0 ms | 212 KB | Output is correct |
| 6 | Correct | 1 ms | 212 KB | Output is correct |
| 7 | Correct | 0 ms | 212 KB | Output is correct |
| 8 | Correct | 1 ms | 296 KB | Output is correct |
| 9 | Correct | 1 ms | 212 KB | Output is correct |
| 10 | Correct | 1 ms | 212 KB | Output is correct |
| 11 | Correct | 1 ms | 212 KB | Output is correct |
| 12 | Correct | 1 ms | 340 KB | Output is correct |
| 13 | Correct | 1 ms | 336 KB | Output is correct |
| 14 | Correct | 1 ms | 340 KB | Output is correct |
| 15 | Correct | 0 ms | 212 KB | Output is correct |
| 16 | Correct | 1 ms | 212 KB | Output is correct |
| 17 | Correct | 1 ms | 340 KB | Output is correct |
| 18 | Correct | 1 ms | 340 KB | Output is correct |
| 19 | Correct | 1 ms | 212 KB | Output is correct |
| 20 | Runtime error | 32 ms | 4428 KB | Execution killed with signal 11 |
| 21 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 212 KB | Output is correct |
| 2 | Correct | 1 ms | 212 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 336 KB | Output is correct |
| 5 | Correct | 0 ms | 212 KB | Output is correct |
| 6 | Correct | 1 ms | 212 KB | Output is correct |
| 7 | Correct | 0 ms | 212 KB | Output is correct |
| 8 | Correct | 1 ms | 296 KB | Output is correct |
| 9 | Correct | 1 ms | 212 KB | Output is correct |
| 10 | Correct | 1 ms | 212 KB | Output is correct |
| 11 | Correct | 1 ms | 212 KB | Output is correct |
| 12 | Correct | 1 ms | 340 KB | Output is correct |
| 13 | Correct | 1 ms | 336 KB | Output is correct |
| 14 | Correct | 1 ms | 340 KB | Output is correct |
| 15 | Correct | 0 ms | 212 KB | Output is correct |
| 16 | Correct | 1 ms | 212 KB | Output is correct |
| 17 | Correct | 1 ms | 340 KB | Output is correct |
| 18 | Correct | 1 ms | 340 KB | Output is correct |
| 19 | Correct | 1 ms | 212 KB | Output is correct |
| 20 | Runtime error | 32 ms | 4428 KB | Execution killed with signal 11 |
| 21 | Halted | 0 ms | 0 KB | - |