oj.uz

Submission #117676

# Submission time Handle Problem Language Result Execution time Memory
117676 2019-06-17T05:57:48 Z 이온조(#2879) Izlet (COI19_izlet) C++14
25 / 100
 842 ms 36268 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct UF {
    int p[3009];
    UF(int sz) {
        for(int i=1; i<=sz; i++) p[i] = i;
    }
    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;
    }
};

UF col(3000);
int N, A[3009][3009], C[3009], p[3009], in[3009], ou[3009], t;
vector<pii> ed;
bool vs[3009];

void go(int n, int par) {
    in[n] = ++t;
    vs[n] = 1; p[n] = par;
    for(int i=1; i<=N; i++) {
        if(!vs[i] && A[n][i] <= 2) {
            go(i, n);
            ed.push_back({i, n});
        }
    }
    ou[n] = ++t;
}

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(A[i][j] == 1) col.merg(i, j);
        }
    }
    go(1, 1);
    for(int i=2; i<=N; i++) {
        for(int j=i+1; j<=N; j++) {
            int a, b, c, d;
            if(in[i] < in[j] && ou[j] < ou[i]) a = p[i], b = i, c = p[j], d = j;
            else if(in[i] > in[j] && ou[j] > ou[i]) a = p[j], b = j, c = p[i], d = i;
            else a = i, b = p[i], c = p[j], d = j;
            if(A[b][c] != A[a][c] && A[b][c] != A[b][d] && A[a][d] == A[b][c] + 1) col.merg(a, d);
        }
    }
    for(int i=1; i<=N; i++) printf("%d ", col.root(i));
    for(auto& it: ed) printf("\n%d %d", it.first, it.second);
    return 0;
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:38: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:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
izlet.cpp:42: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
0 / 18.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 36224 KB Output is correct
2 Correct 678 ms 36216 KB Output is correct
3 Correct 842 ms 36208 KB Output is correct
4 Correct 839 ms 36228 KB Output is correct
5 Correct 671 ms 36268 KB Output is correct
6 Correct 711 ms 36252 KB Output is correct
7 Correct 514 ms 30712 KB Output is correct

Subtask #3
0 / 57.0

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