제출 #1148750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148750		ace5	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	2317 ms	40256 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 2e9;
const int maxn = 505;

vector<pair<int,pair<int,int>>> e;
vector<pair<int,int>> g[maxn];
set<int> tr;
int res = 0;

void dfs_mn(int v,int p,int tmn,int nd)
{
    if(v == nd)
    {
        res = tmn;
        return ;
    }
    for(auto [u,ind]:g[v])
    {
        if(u != p)
        {
            dfs_mn(u,v,min(tmn,ind),nd);
        }
    }
    return ;
}
void dfs_mx(int v,int p,int tmx,int nd)
{
    if(v == nd)
    {
        res = tmx;
        return ;
    }
    for(auto [u,ind]:g[v])
    {
        if(u != p)
        {
            dfs_mx(u,v,max(tmx,ind),nd);
        }
    }
    return ;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < m;++i)
    {
        int a,b,w;
        cin >> a >> b >> w;
        a--;
        b--;
        e.push_back({w,{a,b}});
    }
    sort(e.begin(),e.end());
    vector<pair<pair<int,int>,int>> ev;
    for(int i = 0;i < m;++i)
    {
        for(int j = 0;j < n;++j)
            g[j].clear();
        for(auto ind : tr)
        {
            g[e[ind].second.first].push_back({e[ind].second.second,ind});
            g[e[ind].second.second].push_back({e[ind].second.first,ind});
        }
        res = -1;
        dfs_mn(e[i].second.first,-1,INF,e[i].second.second);
        ev.push_back({{(res == -1 ? 1 : (e[i].first+e[res].first)/2+1),-1},e[i].first});
        ev.push_back({{e[i].first,1},e[i].first});
        tr.erase(res);
        tr.insert(i);
    }
    tr.clear();
    for(int i = m-1;i >= 0;--i)
    {
        for(int j = 0;j < n;++j)
            g[j].clear();
        for(auto ind : tr)
        {
            g[e[ind].second.first].push_back({e[ind].second.second,ind});
            g[e[ind].second.second].push_back({e[ind].second.first,ind});
        }
        res = m;
        dfs_mx(e[i].second.first,-1,-1,e[i].second.second);
        ev.push_back({{e[i].first,-2},e[i].first});
        ev.push_back({{(res == m ? INF : (e[i].first+e[res].first)/2),2},e[i].first});
        tr.erase(res);
        tr.insert(i);
    }
    int q;
    cin >> q;
    ll ans[q];
    for(int i = 0;i < q;++i)
    {
        int x;
        cin >> x;
        ev.push_back({{x,0},i});
    }
    sort(ev.begin(),ev.end());
    ll tres1 = 0,tres2 = 0,k1 = 0,k2 = 0;
    for(int i = 0;i < ev.size();++i)
    {
        if(ev[i].first.second == -1)
        {
            tres1 += ev[i].second;
            k1 ++;
        }
        else if(ev[i].first.second == 1)
        {
            tres1 -= ev[i].second;
            k1--;
        }
        else if(ev[i].first.second == -2)
        {
            tres2 -= ev[i].second;
            k2++;
        }
        else if(ev[i].first.second == 2)
        {
            tres2 += ev[i].second;
            k2--;
        }
        else
            ans[ev[i].second] = tres1 + tres2 + (ev[i].first.first) * (k2-k1);
    }
    for(int i = 0;i < q;++i)
    {
        cout << ans[i] << "\n";
    }
    cout << "\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