Cod sursa(job #1946331)

Utilizator failureJust a Joke failure Data 30 martie 2017 08:12:57
Problema Oras Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>

#define MAXN 201

using namespace std;

bool edge[MAXN][MAXN], answer[MAXN][MAXN];
int n;

bool path(int node, int son) {
    if(edge[node][son])
        return 1;
    int i;
    for(i=1; i<=n; i++)
        if(i != node && i != son)
            if(edge[node][i] && edge[i][son])
                return 1;
    return 0;
}

bool putPath(int node, int son) {
    if(!edge[node][son] && !edge[son][node]) {
        edge[node][son] = 1;
        answer[node][son] = 0;
        answer[son][node] = 1;
        return 1;
    }

    int i;
    for(i=1; i<=n; ++i)
        if(i != node && i != son)
            if(!edge[i][node] && !edge[son][i]) {
                edge[node][i] = 1;
                edge[i][son] = 1;
                answer[node][i] = 0;
                answer[i][node] = 1;
                answer[i][son] = 0;
                answer[son][i] = 1;
                return 1;
            }

    return 0;
}

int main()
{
    freopen("oras.in", "r", stdin);
    freopen("oras.out", "w", stdout);

    int i, j;

    scanf("%d", &n);

    for(i=2; i<=n; ++i)
        for(j=1; j<i; ++j) {
            if(!path(i, j))
                if(!putPath(i, j)) {
                    printf("-1");
                    return 0;
                }
            if(!path(j, i))
                if(!putPath(j, i)) {
                    printf("-1");
                    return 0;
                }
        }

    for(i=1; i<=n; ++i) {
        for(j=1; j<=n; ++j)
            printf("%d", answer[i][j]);
        printf("\n");
    }

    return 0;
}