Submission #874353

#	Time	Username	Problem	Language	Result	Execution time	Memory
874353		winter0101	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	704 ms	135504 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=5e2+9;
const int maxm=1e5+9;
const int maxq=1e6+9;
struct edg{
int u,v,w;
bool operator < (const edg &p){
return w<p.w;
}
}a[maxm];
int f[maxn];
int fs(int u){
if (f[u]<0)return u;
return f[u]=fs(f[u]);
}
bool unite(int u,int v){
u=fs(u),v=fs(v);
if (u==v)return 0;
if (f[u]>f[v])swap(u,v);
f[u]+=f[v];
f[v]=u;
return 1;
}
long long b[maxq];
int l1[maxm],r1[maxm];
vector<int>add[maxq][2];
vector<int>del[maxq][2];
/*voi moi i tim r[i] sao cho unite tu i+1 den r[i] thi se k can unite i
=> khoang can dung khi w[i]<=query se co the la i den r[i]
nhan xet voi moi query thuoc khoang w[i] den w[r[i]] thi goi x la cac tap canh <=query va y la tap con lai
thi bao gio x cung duoc unite truoc i va ta can unite den r[i] thi moi khong can i => khi ma i van dong gop la khi 2*query<w[i]+w[r[i]]
tu do tim khoang r can thiet de duy tri mst
*/
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n,m;
    cin>>n>>m;
    for1(i,1,m)cin>>a[i].u>>a[i].v>>a[i].w;
    sort(a+1,a+1+m);
    int q;
    cin>>q;
    for1(i,1,q)cin>>b[i];
    vector<int>use;
    for1(i,1,m){
    for1(j,1,n)f[j]=-1;
    unite(a[i].u,a[i].v);
    vector<int>nw;
    nw.pb(i);
    for (auto u:use){
    if (unite(a[u].u,a[u].v)){
    nw.pb(u);
    }
    else {
    l1[i]=u;
    r1[u]=i;
    }
    }
    use.swap(nw);
    }
    long long cnt1=0,cnt2=0;
    long long w1=0,w2=0;
    for1(i,1,m){
    if (l1[i]==0){
    cnt2++;
    w2+=a[i].w;
    int l=1,r=q,ans=-1;
    while (l<=r){
    int mid=(l+r)/2;
    if (b[mid]>=a[i].w){
    ans=mid;
    r=mid-1;
    }
    else l=mid+1;
    }
    if (ans!=-1){
    del[ans][1].pb(i);
    add[ans][0].pb(i);
    }
    }
    if (r1[i]==0){
    }
    else {
    int l=1,r=q,ans=-1;
    while (l<=r){
    int mid=(l+r)/2;
    if (2*b[mid]>=a[i].w+a[r1[i]].w){
    ans=mid;
    r=mid-1;;
    }
    else l=mid+1;
    }
    if (ans!=-1){
    del[ans][0].pb(i);
    add[ans][1].pb(r1[i]);
    l=1,r=q,ans=-1;
    while (l<=r){
    int mid=(l+r)/2;
    if (b[mid]>=a[r1[i]].w){
    ans=mid;
    r=mid-1;
    }
    else l=mid+1;
    }
    if (ans!=-1){
    del[ans][1].pb(r1[i]);
    add[ans][0].pb(r1[i]);
    }
    }
    else {
    l=1,r=q,ans=-1;
    while (l<=r){
    int mid=(l+r)/2;
    if (b[mid]>=a[r1[i]].w){
    ans=mid;
    r=mid-1;
    }
    else l=mid+1;
    }
    if (ans!=-1){
    del[ans][0].pb(i);
    add[ans][0].pb(r1[i]);
    }
    }
    }
    }
    for1(i,1,q){
    for (auto v:add[i][0]){
    cnt1++;
    w1+=a[v].w;
    }
    for (auto v:add[i][1]){
    cnt2++;
    w2+=a[v].w;
    }
    for (auto v:del[i][0]){
    cnt1--;
    w1-=a[v].w;
    }
    for (auto v:del[i][1]){
    cnt2--;
    w2-=a[v].w;
    }
    cout<<b[i]*cnt1-w1+w2-b[i]*cnt2<<'\n';
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23