oj.uz

Submission #417897

# Submission time Handle Problem Language Result Execution time Memory
417897 2021-06-04T13:24:26 Z 반딧불(#7603) Rooted MST (innopolis2021_final_E) C++17
10 / 100
 318 ms 11748 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;
    }
} dsu;

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

int cnt[300002];
int ans;

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

    ans = n;
    for(int i=1; i<=n; i++){
        if(dsu.find(i) == i && !cnt[i]) ans++;
    }

    scanf("%d", &q);
    while(q--){
        int i; ll w;
        scanf("%d %lld", &i, &w);
        int x = dsu.find(i);

        if(arr[i] == 1){
            cnt[x]--;
            if(!cnt[x]) ans++;
        }
        arr[i] = w;
        if(arr[i] == 1){
            if(!cnt[x]) ans--;
            cnt[x]++;
        }

        printf("%d\n", ans);
    }
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 11748 KB Output is correct
2 Correct 226 ms 9372 KB Output is correct
3 Correct 186 ms 6472 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 188 ms 6412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 6032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 6032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 318 ms 11740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -