Submission #729752

#	Time	Username	Problem	Language	Result	Execution time	Memory
729752		azberjibiou	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	3015 ms	34404 KiB

reconstruction

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fi first
#define se 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=120;
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;
typedef struct event{
    int t, a, b;
    event() : t(), a(), b() {}
    event(int t, int a, int b) : t(t), a(a), b(b) {}
}event;
int N, M, Q;
edge A[mxM];
pii rng[mxM];
int qry[mxQ];
ll ans[mxQ];
vector <edge> v;
vector <event> tl;
int par[mxN];
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();
    for(int i=0;i<M;i++)
    {
        init_uf();
        assert((int)v.size()<=N);
        for(int j=(int)v.size()-1;j>=0;j--)
        {
            onion(v[j].s, v[j].e);
            if(findpar(A[i].s)==findpar(A[i].e))
            {
                rng[i].fi=(v[j].w+A[i].w+2)/2;
                break;
            }
        }
        v.push_back(A[i]);
        init_uf();
        for(int j=v.size()-1;j>=0;j--)
        {
            if(findpar(v[j].s)==findpar(v[j].e))
            {
                v.erase(v.begin()+j);
                break;
            }
            onion(v[j].s, v[j].e);
        }
    }
    v.clear();
    for(int i=M-1;i>=0;i--)
    {
        rng[i].se=MOD;
        init_uf();
        for(int j=(int)v.size()-1;j>=0;j--)
        {
            onion(v[j].s, v[j].e);
            if(findpar(A[i].s)==findpar(A[i].e))
            {
                rng[i].se=(v[j].w+A[i].w)/2;
                break;
            }
        }
        v.push_back(A[i]);
        init_uf();
        for(int j=v.size()-1;j>=0;j--)
        {
            if(findpar(v[j].s)==findpar(v[j].e))
            {
                v.erase(v.begin()+j);
                break;
            }
            onion(v[j].s, v[j].e);
        }
    }
    for(int i=0;i<M;i++)
    {
        tl.emplace_back(rng[i].fi, -1, A[i].w);
        tl.emplace_back(A[i].w, 2, -2*A[i].w);
        tl.emplace_back(rng[i].se+1, -1, A[i].w);
    }
    sort(all(tl), [](event a, event b){return a.t<b.t;});
    int it=0;
    pll nv=pll(0, 0);
    for(int i=0;i<Q;i++)
    {
        while(it<tl.size() && tl[it].t<=qry[i])    nv.fi+=tl[it].a, nv.se+=tl[it++].b;
        cout << nv.fi*qry[i]+nv.se << '\n';
    }
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:116:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         while(it<tl.size() && tl[it].t<=qry[i])    nv.fi+=tl[it].a, nv.se+=tl[it++].b;
      |               ~~^~~~~~~~~~

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