oj.uz

Submission #117681

# Submission time Handle Problem Language Result Execution time Memory
117681 2019-06-17T06:06:03 Z 이온조(#2879) Izlet (COI19_izlet) C++14
100 / 100
 1141 ms 38392 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 640 KB Output is correct
2 Correct 724 ms 36344 KB Output is correct
3 Correct 729 ms 36348 KB Output is correct
4 Correct 737 ms 36292 KB Output is correct
5 Correct 744 ms 36344 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 36108 KB Output is correct
2 Correct 730 ms 36032 KB Output is correct
3 Correct 837 ms 36148 KB Output is correct
4 Correct 1141 ms 36284 KB Output is correct
5 Correct 700 ms 36032 KB Output is correct
6 Correct 707 ms 35936 KB Output is correct
7 Correct 516 ms 30536 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 724 ms 36344 KB Output is correct
3 Correct 729 ms 36348 KB Output is correct
4 Correct 737 ms 36292 KB Output is correct
5 Correct 744 ms 36344 KB Output is correct
6 Correct 690 ms 36108 KB Output is correct
7 Correct 730 ms 36032 KB Output is correct
8 Correct 837 ms 36148 KB Output is correct
9 Correct 1141 ms 36284 KB Output is correct
10 Correct 700 ms 36032 KB Output is correct
11 Correct 707 ms 35936 KB Output is correct
12 Correct 516 ms 30536 KB Output is correct
13 Correct 755 ms 36088 KB Output is correct
14 Correct 810 ms 38284 KB Output is correct
15 Correct 735 ms 38180 KB Output is correct
16 Correct 818 ms 37912 KB Output is correct
17 Correct 834 ms 38140 KB Output is correct
18 Correct 729 ms 38288 KB Output is correct
19 Correct 756 ms 38188 KB Output is correct
20 Correct 745 ms 38392 KB Output is correct
21 Correct 754 ms 37476 KB Output is correct
22 Correct 734 ms 38032 KB Output is correct
23 Correct 761 ms 37548 KB Output is correct
24 Correct 795 ms 38188 KB Output is correct
25 Correct 740 ms 38092 KB Output is correct