제출 #914141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914141		Shayan86	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	1426 ms	46548 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

const ll N = 507;
const ll M = 1e5 + 50;
const ll Q = 1e6 + 50;
const ll Mod = 1e9 + 7;

int n, m, q, lt[M], rt[M], qu[Q], par[N], sz[N];
ll zp[Q], sum[Q];

vector<pair<int, pii>> edge;

int getPar(int v){
    return (par[v] == v ? v : par[v] = getPar(par[v]));
}

bool Union(int u, int v){
    u = getPar(u);
    v = getPar(v);
    if(u == v) return false;
    if(sz[v] < sz[u]) swap(u, v);
    sz[v] += sz[u]; par[u] = v;
    return true;
}

int main(){
    fast_io;

    cin >> n >> m;

    int u, v, w;
    for(int i = 1; i <= m; i++){
        cin >> u >> v >> w;
        edge.pb({w, {u, v}});
    }
    sort(all(edge));

    cin >> q;
    for(int i = 0; i < q; i++) cin >> qu[i];

    for(int i = 0; i < m; i++){
        for(int j = 1; j <= n; j++){
            sz[j] = 1; par[j] = j;
        }

        int u = edge[i].S.F;
        int v = edge[i].S.S;
        int w = edge[i].F;

        lt[i] = -1;
        for(int j = i-1; j >= 0; j--){
            bool ch = Union(edge[j].S.F, edge[j].S.S);
            if(ch && getPar(u) == getPar(v)){
                lt[i] = j; break;
            }
        }
    }
    for(int i = 0; i < m; i++){
        for(int j = 1; j <= n; j++){
            sz[j] = 1; par[j] = j;
        }

        int u = edge[i].S.F;
        int v = edge[i].S.S;
        int w = edge[i].F;

        rt[i] = m;
        for(int j = i+1; j < m; j++){
            bool ch = Union(edge[j].S.F, edge[j].S.S);
            if(ch && getPar(u) == getPar(v)){
                rt[i] = j; break;
            }
        }
    }

    //for(int i = 0; i < m; i++) cout << lt[i] << sep << rt[i] << endl;

    for(int i = 0; i < m; i++){
        int p1 = 0;
        if(lt[i] != -1) p1 = lower_bound(qu, qu + q, (edge[i].F + edge[lt[i]].F + 1)/2) - qu;

        int p2 = lower_bound(qu, qu + q, edge[i].F) - qu;

        int p3 = q;
        if(rt[i] != m) p3 = lower_bound(qu, qu + q, (edge[i].F + edge[rt[i]].F - 1) / 2 + 1) - qu;

        //cout << edge[i].F << sep << edge[i].S.F << sep << edge[i].S.S << sep << p1 << sep << p2 << sep << p3 << endl;
        sum[p1] += edge[i].F;
        sum[p2] -= 2*edge[i].F;
        sum[p3] += edge[i].F;
        zp[p1]--;
        zp[p2] += 2;
        zp[p3]--;
    }

    for(int i = 1; i < q; i++){
        sum[i] += sum[i-1]; zp[i] += zp[i-1];
    }

    for(int i = 0; i < q; i++){
        ll res = sum[i] + zp[i] * qu[i];
        cout << res << endl;
        //cout << res << sep << sum[i] << sep << zp[i] << endl;
    }

}

컴파일 시 표준 에러 (stderr) 메시지

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:69:13: warning: unused variable 'w' [-Wunused-variable]
   69 |         int w = edge[i].F;
      |             ^
reconstruction.cpp:86:13: warning: unused variable 'w' [-Wunused-variable]
   86 |         int w = edge[i].F;
      |             ^

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