oj.uz

Submission #596822

# Submission time Handle Problem Language Result Execution time Memory
596822 2022-07-15T07:04:42 Z 반딧불(#8447) Reconstruction Project (JOI22_reconstruction) C++17
0 / 100
 1153 ms 1048576 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]);
    }
}

vector<pair<ll, int> > edgeInversion;

void calculateEdgeInversion(){
    for(int i=1; i<=m; i++){
        for(int j=i+1; j<=m; j++){
            if(arr[i].w == arr[j].w) continue;
            edgeInversion.push_back(make_pair((arr[i].w+arr[j].w+1)/2, arr[i].w>arr[j].w ? i : j));
        }
        edgeInversion.push_back(make_pair(arr[i].w, -i));
    }
    sort(edgeInversion.begin(), edgeInversion.end());
}

vector<dat> link[502];
ll currentTime;
ll ta, tb;
bool isUsed[1002];

void makeInitialGraph(){
    vector<Edge> vec (arr+1, arr+m+1);
    sort(vec.begin(), vec.end());
    dsu.init(n);
    for(Edge edge: vec){
        if(dsu.find(edge.x) == dsu.find(edge.y)) continue;
        dsu.merge(edge.x, edge.y);
        ta-=1, tb+=edge.w;
        link[edge.x].push_back(dat(edge.y, edge.w, edge.idx));
        link[edge.y].push_back(dat(edge.x, edge.w, edge.idx));
        isUsed[edge.idx] = 1;
    }
}

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 tw = abs(currentTime - y.w);
        int tmp = findMinEdge(y.v, x, goal, max(minV, tw), minV<tw?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 processQueries(){
    int pnt = 0;
    for(int i=1; i<=q; i++){
        while(pnt < (int)edgeInversion.size() && edgeInversion[pnt].first <= query[i]){
            pair<ll, int> tmp = edgeInversion[pnt];
            if(tmp.second < 0){ /// �ּ����� ����
                tmp.second *= -1;
                if(isUsed[tmp.second]) ta += 2, tb -= tmp.first*2;
            }
            else{ /// �������� ����
                if(isUsed[tmp.second]){
                    pnt++;
                    continue;
                }
                Edge edge = arr[tmp.second];
                currentTime = tmp.first;
                int tmin = findMinEdge(edge.x, -1, edge.y, -INT_MAX, -1);
                if(abs(arr[tmin].w - currentTime) >= abs(edge.w - currentTime)){
                    eraseLink(arr[tmin].x, tmin);
                    eraseLink(arr[tmin].y, tmin);
                    ta -= (currentTime >= arr[tmin].w ? 1 : -1);
                    tb -= arr[tmin].w * (currentTime >= arr[tmin].w ? -1 : 1);
                    isUsed[tmin] = 0;

                    link[edge.x].push_back(dat(edge.y, edge.w, edge.idx));
                    link[edge.y].push_back(dat(edge.x, edge.w, edge.idx));
                    ta += (currentTime >= edge.w ? 1 : -1);
                    tb += edge.w * (currentTime >= edge.w ? -1 : 1);
                    isUsed[edge.idx] = 1;
                }
            }
            pnt++;
        }

        currentTime = query[i];
        printf("%lld\n", ta * currentTime + tb);
    }
}

void operate(){
    calculateEdgeInversion();
    makeInitialGraph();
    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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Runtime error 1153 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -