제출 #729728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
729728		azberjibiou	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5020 ms	7764 KiB

reconstruction

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pmax pair<ll, ll>
#define all(v) v.begin(), v.end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=520;
const int mxM=100020;
const int mxK=320;
const int mxQ=1000020;
const int MOD=1000000007;
const ll P1=1000000007, P2=10000000009;
const ll INF=8000000000000000001;
typedef struct edge{
    int s, e, w;
}edge;
int N, M, Q, K;
edge A[mxM];
int qry[mxQ];
ll ans[mxQ];
int par[mxN];
edge v1[mxN+mxK], v2[mxN+mxK];
int iv1, iv2;
void init_uf(){for(int i=1;i<=N;i++)   par[i]=i;}
void input()
{
    cin >> N >> M;
    for(int i=0;i<M;i++)   cin >> A[i].s >> A[i].e >> A[i].w;
    sort(A, A+M, [](edge a, edge b){return a.w<b.w;});
    cin >> Q;
    for(int i=0;i<Q;i++)   cin >> qry[i];
}
int findpar(int a){return par[a]==a ? a : par[a]=findpar(par[a]);}
void onion(int a, int b){int p=findpar(a), q=findpar(b);    par[p]=q;}
int main()
{
    gibon
    input();
    K=min(M, 300);
    int qidx=0;
    for(int i=0;i*K<M;i++)
    {
        int s=i*K, e=min((i+1)*K-1, M-1);
        iv1=iv2=0;
        init_uf();
        for(int j=s-1;j>=0;j--)
        {
            if(findpar(A[j].s)!=findpar(A[j].e))
            {
                onion(A[j].s, A[j].e);
                v1[iv1++]=A[j];
            }
        }
        reverse(v1, v1+iv1);
        init_uf();
        for(int j=e+1;j<M;j++)
        {
            if(findpar(A[j].s)!=findpar(A[j].e))
            {
                onion(A[j].s, A[j].e);
                v2[iv2++]=A[j];
            }
        }
        reverse(v2, v2+iv2);
        for(int j=e;j>=s;j--)   v2[iv2++]=A[j];
        while(qidx!=Q && (e==M-1 || qry[qidx]<A[e+1].w))
        {
            int nv=qry[qidx];
            while(iv2!=0 && v2[iv2-1].w<nv)
            {
                v1[iv1++]=v2[iv2-1];
                iv2--;
            }
            int i1=iv1-1, i2=iv2-1;
            init_uf();
            while(i1>=0 && i2>=0)
            {
                if(nv-v1[i1].w<v2[i2].w-nv)
                {
                    if(findpar(v1[i1].s)!=findpar(v1[i1].e))
                    {
                        onion(v1[i1].s, v1[i1].e);
                        ans[qidx]+=nv-v1[i1].w;
                    }
                    i1--;
                }
                else
                {
                    if(findpar(v2[i2].s)!=findpar(v2[i2].e))
                    {
                        onion(v2[i2].s, v2[i2].e);
                        ans[qidx]+=v2[i2].w-nv;
                    }
                    i2--;
                }
            }
            while(i1>=0)
            {
                if(findpar(v1[i1].s)!=findpar(v1[i1].e))
                {
                    onion(v1[i1].s, v1[i1].e);
                    ans[qidx]+=nv-v1[i1].w;
                }
                i1--;
            }
            while(i2>=0)
            {
                if(findpar(v2[i2].s)!=findpar(v2[i2].e))
                {
                    onion(v2[i2].s, v2[i2].e);
                    ans[qidx]+=v2[i2].w-nv;
                }
                i2--;
            }
            qidx++;
        }
    }
    for(int i=0;i<Q;i++)    cout << ans[i] << '\n';
}

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