oj.uz

Submission #117917

# Submission time Handle Problem Language Result Execution time Memory
117917 2019-06-17T12:25:00 Z onjo0127 Izlet (COI19_izlet) C++11
100 / 100
 1014 ms 37512 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), ver(3000);
int N, A[3009][3009], C[3009], p[3009], in[3009], ou[3009], t;
vector<int> adj[3009];

void go(int n, int par) {
    in[n] = ++t;
    p[n] = par;
    for(auto& i: adj[n]) if(i != par) go(i, n);
    ou[n] = ++t;
}

void addedge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
    ver.merg(u, v);
}

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);
                if(ver.root(i) != ver.root(j)) addedge(i, j);
            }
        }
    }
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            if(A[i][j] == 2 && ver.root(i) != ver.root(j)) {
                addedge(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(int i=1; i<=N; i++) for(auto& it: adj[i]) if(i < it) printf("\n%d %d", i, it);
    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
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 794 ms 37212 KB Output is correct
3 Correct 779 ms 37232 KB Output is correct
4 Correct 747 ms 37128 KB Output is correct
5 Correct 727 ms 37060 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 36264 KB Output is correct
2 Correct 760 ms 37240 KB Output is correct
3 Correct 1014 ms 36856 KB Output is correct
4 Correct 836 ms 36732 KB Output is correct
5 Correct 699 ms 37284 KB Output is correct
6 Correct 705 ms 36612 KB Output is correct
7 Correct 517 ms 31084 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 794 ms 37212 KB Output is correct
3 Correct 779 ms 37232 KB Output is correct
4 Correct 747 ms 37128 KB Output is correct
5 Correct 727 ms 37060 KB Output is correct
6 Correct 698 ms 36264 KB Output is correct
7 Correct 760 ms 37240 KB Output is correct
8 Correct 1014 ms 36856 KB Output is correct
9 Correct 836 ms 36732 KB Output is correct
10 Correct 699 ms 37284 KB Output is correct
11 Correct 705 ms 36612 KB Output is correct
12 Correct 517 ms 31084 KB Output is correct
13 Correct 752 ms 36588 KB Output is correct
14 Correct 798 ms 36588 KB Output is correct
15 Correct 732 ms 37512 KB Output is correct
16 Correct 798 ms 36700 KB Output is correct
17 Correct 883 ms 36604 KB Output is correct
18 Correct 726 ms 37364 KB Output is correct
19 Correct 762 ms 37372 KB Output is correct
20 Correct 765 ms 37280 KB Output is correct
21 Correct 738 ms 36528 KB Output is correct
22 Correct 731 ms 37372 KB Output is correct
23 Correct 753 ms 36600 KB Output is correct
24 Correct 793 ms 36716 KB Output is correct
25 Correct 725 ms 37152 KB Output is correct