oj.uz

Submission #117668

# Submission time Handle Problem Language Result Execution time Memory
117668 2019-06-17T05:31:53 Z 이온조(#2879) Izlet (COI19_izlet) C++14
43 / 100
 856 ms 38132 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int N;
int A[3009][3009], C[3009], p[3009];
vector<pii> ed;

int root(int x) {
    if(p[x] == x) return x;
    return p[x] = root(p[x]);
}

void merg(int u, int v) {
    u = root(u); v = root(v);
    p[u] = v;
}

void go(int n, int c) {
    C[n] = c;
    for(int i=1; i<=N; i++) {
        if(!C[i] && A[n][i] == 1) {
            go(i, c);
            ed.push_back({n, i});
        }
    }
}

int main() {
    int sub; scanf("%d",&sub);
    scanf("%d",&N);
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            scanf("%d",&A[i][j]);
        }
    }
    if(sub == 1) {
        int c = 1, p = -1;
        for(int i=1; i<=N; i++) if(!C[i]) {
            if(p != -1) ed.push_back({i, p});
            go(i, c);
            c = 3 - c;
            p = i;
        }
        for(int i=1; i<=N; i++) printf("%d ", C[i]);
        for(auto& it: ed) printf("\n%d %d", it.first, it.second);
    }
    if(sub == 2) {
        for(int i=1; i<=N; i++) p[i] = i;
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(A[i][j] == 1) merg(i, j);
            }
        }
        for(int i=2; i<N; i++) {
            for(int j=i; j<N; j++) {
                if(A[i][j] != A[i-1][j] && A[i][j] != A[i][j+1] && A[i-1][j+1] == A[i][j] + 1) merg(i-1, j+1);
            }
        }
        for(int i=1; i<=N; i++) printf("%d ", root(i));
        for(int i=2; i<=N; i++) printf("\n%d %d", i-1, i);
    }
    return 0;
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:30:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int sub; scanf("%d",&sub);
              ~~~~~^~~~~~~~~~~
izlet.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
izlet.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&A[i][j]);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 691 ms 35856 KB Output is correct
3 Correct 692 ms 35988 KB Output is correct
4 Correct 700 ms 36124 KB Output is correct
5 Correct 703 ms 36216 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 35948 KB Output is correct
2 Correct 730 ms 37732 KB Output is correct
3 Correct 844 ms 38132 KB Output is correct
4 Correct 856 ms 37856 KB Output is correct
5 Correct 715 ms 37688 KB Output is correct
6 Correct 726 ms 37680 KB Output is correct
7 Correct 523 ms 32100 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 691 ms 35856 KB Output is correct
3 Correct 692 ms 35988 KB Output is correct
4 Correct 700 ms 36124 KB Output is correct
5 Correct 703 ms 36216 KB Output is correct
6 Correct 740 ms 35948 KB Output is correct
7 Correct 730 ms 37732 KB Output is correct
8 Correct 844 ms 38132 KB Output is correct
9 Correct 856 ms 37856 KB Output is correct
10 Correct 715 ms 37688 KB Output is correct
11 Correct 726 ms 37680 KB Output is correct
12 Correct 523 ms 32100 KB Output is correct
13 Incorrect 698 ms 37348 KB Unexpected end of file - int32 expected
14 Halted 0 ms 0 KB -