oj.uz

답안 #417902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
417902 2021-06-04T13:30:58 Z 반딧불(#7603) Rooted MST (innopolis2021_final_E) C++17
0 / 100
 4000 ms 44460 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge{
    int x, y; ll z;
    Edge(){}
    Edge(int x, int y, ll z): x(x), y(y), z(z){}

    bool operator<(const Edge &r)const{
        return z > r.z;
    }
};

struct DisjointSet{
    int n;
    int par[300002];

    void init(int _n){
        n = _n;
        for(int i=0; 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;
    }
};

int n, m, q;
ll arr[300002];
Edge link[300002];

ll dflt;
ll lim;

ll printMST(){
    priority_queue<Edge> pq;
    for(int i=1; i<=m; i++) pq.push(link[i]);
    for(int i=1; i<=n; i++){
        pq.push(Edge(0, i, arr[i]));
    }

    DisjointSet dsu;
    dsu.init(n);

    ll ans = 0;
    while(!pq.empty()){
        Edge tmp = pq.top(); pq.pop();
        int x = tmp.x, y = tmp.y;
        if(dsu.find(x) == dsu.find(y)) continue;
        dsu.merge(x, y);
        ans += tmp.z;
    }
    return ans;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%lld", &arr[i]);
    }
    for(int i=1; i<=m; i++){
        scanf("%d %d %lld", &link[i].x, &link[i].y, &link[i].z);
    }

    arr[1] = 0;
    dflt = printMST();

    ll MIN = 0, MAX = 1e9 + 1, ANS = 0;
    while(MIN <= MAX){
        ll MID = (MIN + MAX) / 2;
        arr[1] = MID;
        if(printMST() == dflt + MID){
            ANS = MID;
            MIN = MID + 1;
        }
        else MAX = MID - 1;
    }
    lim = ANS;

    scanf("%d", &q);
    while(q--){
        ll x;
        scanf("%lld %lld", &x, &x);
        printf("%lld\n", dflt + min(lim, x));
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%lld", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d %d %lld", &link[i].x, &link[i].y, &link[i].z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf("%lld %lld", &x, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4067 ms 34460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2504 ms 19260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2852 ms 17116 KB Output is correct
2 Correct 2880 ms 20284 KB Output is correct
3 Correct 2912 ms 20564 KB Output is correct
4 Correct 2325 ms 24476 KB Output is correct
5 Correct 1380 ms 15588 KB Output is correct
6 Correct 362 ms 10336 KB Output is correct
7 Execution timed out 4083 ms 44460 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2852 ms 17116 KB Output is correct
2 Correct 2880 ms 20284 KB Output is correct
3 Correct 2912 ms 20564 KB Output is correct
4 Correct 2325 ms 24476 KB Output is correct
5 Correct 1380 ms 15588 KB Output is correct
6 Correct 362 ms 10336 KB Output is correct
7 Execution timed out 4083 ms 44460 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4086 ms 34504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1532 KB Output isn't correct
2 Halted 0 ms 0 KB -