Submission #117917

#	Time	Username	Problem	Language	Result	Execution time	Memory
117917		onjo0127	Izlet (COI19_izlet)	C++11	100 / 100	1014 ms	37512 KiB

izlet

#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 (stderr)

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 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57