제출 #637984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637984		Cross_Ratio	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	1712 ms	30388 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll A[2005];
ll B[2005];
ll C[2005]; // C[i] <= x < C[i+1], ans = x * A[i] + B[i];
typedef pair<ll, ll> P;
ll dis[505][505];
ll dis2[505][505];
struct UnionFind {
    vector<int> root;
    UnionFind(int n) {
        root.resize(n);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        root[n] = r;
        return r;
    }
    void Merge(int x, int y) {
        x = Find(x), y = Find(y);
        if(x==y) return;
        if(root[x]>root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
    }
};
vector<array<ll, 4>> Tree;
vector<set<array<ll, 4>>> adj;
array<ll, 4> Edge[100005];
bool S[100005];
vector<vector<array<int, 2>>> E;
vector<array<int, 3>> E2;
ll val[505];
ll par[505];
ll dep[505];
ll pid[505];
ll tid[100005];
void dfs(int c, int p, int d, int d2) {
    par[c] = p;
    dep[c] = d;
    pid[c] = d2;
    for(auto it : adj[c]) {
        if(it[0]==p) continue;
        dfs(it[0], c, d+1, it[2]);
    }
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    clock_t st = clock();
    adj.resize(N);
    int i, j;
    E.resize(N);
    for(i=0;i<M;i++) {
        int a, b, c;
        cin >> a>>b>>c;
        Edge[i] = {c, a-1, b-1, i};
    }
    for(i=0;i<M;i++) tid[i] = -1;
    sort(Edge, Edge+M);
    UnionFind UF(N);
    int cnt = 0;
    for(i=0;i<M;i++) {
        Edge[i][3] = i;
        if(UF.Find(Edge[i][1])==UF.Find(Edge[i][2])) continue;
        UF.Merge(Edge[i][1], Edge[i][2]);
        S[i] = true;
        adj[Edge[i][1]].insert({Edge[i][2], Edge[i][0], i});
        adj[Edge[i][2]].insert({Edge[i][1], Edge[i][0], i});
        val[cnt] = Edge[i][0];
        tid[i] = cnt;
        cnt++;
    }
    for(i=0;i<M;i++) {
        if(!S[i]) {
            dfs(0, -1, 0, -1);
            int a = Edge[i][1];
            int b = Edge[i][2];
            if(dep[a]<dep[b]) swap(a, b);
            ll val = INF, id = -1;
            while(dep[a]>dep[b]) {
                if(val > Edge[pid[a]][0]) {
                    val = Edge[pid[a]][0];
                    id = pid[a];
                }
                a = par[a];
            }
            while(a!=b) {
                if(val > Edge[pid[a]][0]) {
                    val = Edge[pid[a]][0];
                    id = pid[a];
                }
                if(val > Edge[pid[b]][0]) {
                    val = Edge[pid[b]][0];
                    id = pid[b];
                }
                a = par[a];
                b = par[b];
            }
            ll val2 = Edge[i][0];
            if(val <= val2) {
                ll time = (val2 + val + 1) / 2;
                E2.push_back({time, i, id});
                S[i] = true;
                S[id] = false;
                adj[Edge[id][1]].erase({Edge[id][2], Edge[id][0], id});
                adj[Edge[id][2]].erase({Edge[id][1], Edge[id][0], id});
                adj[Edge[i][1]].insert({Edge[i][2], Edge[i][0], i});
                adj[Edge[i][2]].insert({Edge[i][1], Edge[i][0], i});
            }
        }
    }
    sort(E2.begin(),E2.end());
    int Q;
    cin >> Q;
    int pt = -1;
    while(Q--) {
        ll x;
        ll ans = 0;
        cin >> x;
        while(pt+1<E2.size()&&x>=E2[pt+1][0]) {
            pt++;
            int id1 = E2[pt][1], id2 = E2[pt][2];
            tid[id1] = tid[id2];
            tid[id2] = -1;
            val[tid[id1]] = Edge[id1][0];
        }
        for(i=0;i<N-1;i++) ans += abs(x - val[i]);
        cout << ans << '\n';
    }
}

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

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:110:31: warning: narrowing conversion of 'time' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  110 |                 E2.push_back({time, i, id});
      |                               ^~~~
reconstruction.cpp:110:40: warning: narrowing conversion of 'id' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  110 |                 E2.push_back({time, i, id});
      |                                        ^~
reconstruction.cpp:128:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         while(pt+1<E2.size()&&x>=E2[pt+1][0]) {
      |               ~~~~^~~~~~~~~~
reconstruction.cpp:57:13: warning: unused variable 'st' [-Wunused-variable]
   57 |     clock_t st = clock();
      |             ^~
reconstruction.cpp:59:12: warning: unused variable 'j' [-Wunused-variable]
   59 |     int i, j;
      |            ^

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