oj.uz

Submission #611392

# Submission time Handle Problem Language Result Execution time Memory
611392 2022-07-29T04:48:21 Z 반딧불(#8497) Izlet (COI19_izlet) C++17
18 / 100
 724 ms 53284 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct unionFind{
    int par[3002];
    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;

int n;
int arr[3002][3002];
vector<int> ans;
int col = 1;
int colans[3002];

int main(){
    scanf("%d %d", &n, &n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%d", &arr[i][j]);
        }
    }
    dsu.init(n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(arr[i][j] == 1) dsu.merge(i, j);
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(dsu.find(j)==i) ans.push_back(j);
        }
    }
    for(int i=0; i<n; i++){
        if(i && dsu.find(ans[i]) != dsu.find(ans[i-1])) col = 3-col;
        colans[ans[i]] = col;
    }
    for(int i=1; i<=n; i++) printf("%d ", colans[i]);
    puts("");
    for(int i=0; i<n-1; i++) printf("%d %d\n", ans[i], ans[i+1]);
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d %d", &n, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
izlet.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |             scanf("%d", &arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 666 ms 53220 KB Output is correct
3 Correct 671 ms 53144 KB Output is correct
4 Correct 724 ms 53108 KB Output is correct
5 Correct 697 ms 52984 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 666 ms 53220 KB Output is correct
3 Correct 671 ms 53144 KB Output is correct
4 Correct 724 ms 53108 KB Output is correct
5 Correct 697 ms 52984 KB Output is correct
6 Incorrect 644 ms 53284 KB Output isn't correct
7 Halted 0 ms 0 KB -