oj.uz

Submission #596816

# Submission time Handle Problem Language Result Execution time Memory
596816 2022-07-15T06:25:18 Z 반딧불(#8447) Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 416544 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int v, w, idx;
    dat(){}
    dat(int v, int w, int idx): v(v), w(w), idx(idx){}
};

struct unionFind{
    int par[1002];

    void init(int _n){
        for(int i=1; i<=_n; i++) par[i] = i;
    }

    int find(int x){
        if(x == par[x]) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        par[x] = y;
    }
} dsu;

struct Edge{
    int x, y; ll w;
    int idx;
    Edge(){}
    Edge(int x, int y, ll w): x(x), y(y), w(w){}
    bool operator<(const Edge &r)const{
        return w<r.w;
    }
};

void input();
void operate();

int main(){
    input();
    operate();
}

int n, m, q;
Edge arr[100002];
ll query[1000002];

void input(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        scanf("%d %d %lld", &arr[i].x, &arr[i].y, &arr[i].w);
    }
    sort(arr+1, arr+m+1);
    for(int i=1; i<=m; i++) arr[i].idx = i;

    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        scanf("%lld", &query[i]);
    }
}

int lloc[1000002], rloc[1000002];
bool haslloc[100002], hasrloc[100002];

void findQueryLocations(){ /// �� �������� �����ϴ� ����ġ�� �̺� Ž��
    for(int i=1; i<=q; i++){
        int l = 1, r = m;
        while(l<=r){
            int mid = (l+r)/2;
            if(arr[mid].w <= query[i]) lloc[i] = mid, l = mid+1;
            else r = mid-1;
        }

        l = 1, r = m;
        rloc[i] = m+1;
        while(l<=r){
            int mid = (l+r)/2;
            if(query[i] <= arr[mid].w) rloc[i] = mid, r = mid-1;
            else l = mid+1;
        }

        haslloc[lloc[i]] = hasrloc[rloc[i]] = 1;
    }
}

vector<int> lEdge[100002], rEdge[100002];
vector<dat> link[502];

int findMinEdge(int x, int p, int goal, int minV, int minIdx){
    if(goal == x) return minIdx;
    for(dat y: link[x]){
        if(y.v == p) continue;
        int tmp = findMinEdge(y.v, x, goal, min(minV, y.w), minV>y.w?y.idx:minIdx);
        if(tmp) return tmp;
    }
    return 0;
}

void eraseLink(int x, int idx){
    for(auto it = link[x].begin(); it != link[x].end(); ++it){
        if(it->idx == idx){
            link[x].erase(it);
            return;
        }
    }
    exit(1);
}

void makeEdgeList(){
    dsu.init(n);
    vector<int> edgeVec;
    for(int i=1; i<=m; i++){ /// ����ġ�� ���� edge���� ����
        if(dsu.find(arr[i].x) != dsu.find(arr[i].y)){
            dsu.merge(arr[i].x, arr[i].y);
            edgeVec.push_back(arr[i].idx);
            link[arr[i].x].push_back(dat(arr[i].y, arr[i].w, arr[i].idx));
            link[arr[i].y].push_back(dat(arr[i].x, arr[i].w, arr[i].idx));
        }
        else{
            /// ���� �ϳ��� ���� �����ؾ� ��
            int toDelete = findMinEdge(arr[i].x, -1, arr[i].y, INT_MAX, -1);
            Edge edge = arr[toDelete];
            edgeVec.erase(find(edgeVec.begin(), edgeVec.end(), toDelete));
            eraseLink(edge.x, edge.idx);
            eraseLink(edge.y, edge.idx);

            /// �������� ������ �߰�
            edgeVec.push_back(arr[i].idx);
            link[arr[i].x].push_back(dat(arr[i].y, arr[i].w, arr[i].idx));
            link[arr[i].y].push_back(dat(arr[i].x, arr[i].w, arr[i].idx));
        }
        if(haslloc[i]) lEdge[i] = edgeVec;
    }

    dsu.init(n);
    for(int i=1; i<=n; i++) link[i].clear();
    edgeVec.clear();
    for(int i=m; i>=1; i--){ /// ����ġ�� ū edge���� ����
        if(dsu.find(arr[i].x) != dsu.find(arr[i].y)){
            dsu.merge(arr[i].x, arr[i].y);
            edgeVec.push_back(arr[i].idx);
            link[arr[i].x].push_back(dat(arr[i].y, -arr[i].w, arr[i].idx));
            link[arr[i].y].push_back(dat(arr[i].x, -arr[i].w, arr[i].idx));
        }
        else{
            /// ���� �ϳ��� ���� �����ؾ� ��
            int toDelete = findMinEdge(arr[i].x, -1, arr[i].y, INT_MAX, -1);
            Edge edge = arr[toDelete];
            edgeVec.erase(find(edgeVec.begin(), edgeVec.end(), toDelete));
            eraseLink(edge.x, edge.idx);
            eraseLink(edge.y, edge.idx);

            /// �������� ������ �߰�
            edgeVec.push_back(arr[i].idx);
            link[arr[i].x].push_back(dat(arr[i].y, -arr[i].w, arr[i].idx));
            link[arr[i].y].push_back(dat(arr[i].x, -arr[i].w, arr[i].idx));
        }
        if(hasrloc[i]) rEdge[i] = edgeVec;
    }
}

ll ans[1000002];

void processQueries(){
    for(int i=1; i<=q; i++){
        vector<Edge> edgeVec;
        for(auto x: lEdge[lloc[i]]) edgeVec.push_back(arr[x]);
        for(auto x: rEdge[rloc[i]]) edgeVec.push_back(arr[x]);
        for(Edge &e: edgeVec) e.w = abs(e.w - query[i]);
        sort(edgeVec.begin(), edgeVec.end());
        dsu.init(n);

        ll ans = 0;
        for(Edge &e: edgeVec){
            if(dsu.find(e.x) == dsu.find(e.y)) continue;
            ans += e.w;
            dsu.merge(e.x, e.y);
        }
        printf("%lld\n", ans);
    }
}

void operate(){
    findQueryLocations();
    makeEdgeList();
    processQueries();
}

Compilation message

reconstruction.cpp: In function 'void input()':
reconstruction.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
reconstruction.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d %d %lld", &arr[i].x, &arr[i].y, &arr[i].w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
reconstruction.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%lld", &query[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4984 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5060 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5024 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5024 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4984 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5060 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5024 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5024 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 879 ms 8832 KB Output is correct
21 Correct 414 ms 8148 KB Output is correct
22 Correct 647 ms 8144 KB Output is correct
23 Correct 639 ms 8040 KB Output is correct
24 Correct 659 ms 8068 KB Output is correct
25 Correct 820 ms 8040 KB Output is correct
26 Correct 856 ms 8040 KB Output is correct
27 Correct 861 ms 8296 KB Output is correct
28 Correct 822 ms 8052 KB Output is correct
29 Correct 648 ms 8016 KB Output is correct
30 Correct 851 ms 8180 KB Output is correct
31 Correct 843 ms 8048 KB Output is correct
32 Correct 850 ms 8072 KB Output is correct
33 Correct 858 ms 8180 KB Output is correct
34 Correct 581 ms 8076 KB Output is correct
35 Correct 823 ms 7992 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Execution timed out 5069 ms 416544 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4984 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5060 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5024 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5024 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct
19 Correct 3 ms 5028 KB Output is correct
20 Execution timed out 5038 ms 27600 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4984 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5060 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5024 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5024 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 879 ms 8832 KB Output is correct
21 Correct 414 ms 8148 KB Output is correct
22 Correct 647 ms 8144 KB Output is correct
23 Correct 639 ms 8040 KB Output is correct
24 Correct 659 ms 8068 KB Output is correct
25 Correct 820 ms 8040 KB Output is correct
26 Correct 856 ms 8040 KB Output is correct
27 Correct 861 ms 8296 KB Output is correct
28 Correct 822 ms 8052 KB Output is correct
29 Correct 648 ms 8016 KB Output is correct
30 Correct 851 ms 8180 KB Output is correct
31 Correct 843 ms 8048 KB Output is correct
32 Correct 850 ms 8072 KB Output is correct
33 Correct 858 ms 8180 KB Output is correct
34 Correct 581 ms 8076 KB Output is correct
35 Correct 823 ms 7992 KB Output is correct
36 Correct 2518 ms 76192 KB Output is correct
37 Correct 1584 ms 72252 KB Output is correct
38 Correct 2009 ms 75116 KB Output is correct
39 Correct 2173 ms 75632 KB Output is correct
40 Correct 2222 ms 76140 KB Output is correct
41 Correct 2394 ms 75788 KB Output is correct
42 Correct 2387 ms 76256 KB Output is correct
43 Correct 2491 ms 75872 KB Output is correct
44 Correct 1590 ms 12548 KB Output is correct
45 Correct 1040 ms 8376 KB Output is correct
46 Correct 2420 ms 74316 KB Output is correct
47 Correct 2452 ms 74340 KB Output is correct
48 Correct 2364 ms 64576 KB Output is correct
49 Correct 2393 ms 64552 KB Output is correct
50 Correct 812 ms 8200 KB Output is correct
51 Correct 2015 ms 8284 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4984 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5060 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5024 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5024 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 879 ms 8832 KB Output is correct
21 Correct 414 ms 8148 KB Output is correct
22 Correct 647 ms 8144 KB Output is correct
23 Correct 639 ms 8040 KB Output is correct
24 Correct 659 ms 8068 KB Output is correct
25 Correct 820 ms 8040 KB Output is correct
26 Correct 856 ms 8040 KB Output is correct
27 Correct 861 ms 8296 KB Output is correct
28 Correct 822 ms 8052 KB Output is correct
29 Correct 648 ms 8016 KB Output is correct
30 Correct 851 ms 8180 KB Output is correct
31 Correct 843 ms 8048 KB Output is correct
32 Correct 850 ms 8072 KB Output is correct
33 Correct 858 ms 8180 KB Output is correct
34 Correct 581 ms 8076 KB Output is correct
35 Correct 823 ms 7992 KB Output is correct
36 Correct 2 ms 4948 KB Output is correct
37 Correct 2 ms 4948 KB Output is correct
38 Correct 3 ms 4948 KB Output is correct
39 Execution timed out 5069 ms 416544 KB Time limit exceeded
40 Halted 0 ms 0 KB -