Submission #659806

#	Time	Username	Problem	Language	Result	Execution time	Memory
659806		Neacsu_Mihai	Ronald (COCI17_ronald)	C++14	120 / 120	31 ms	1328 KiB

ronald

#include <bits/stdc++.h>

#define NMAX 1000
#define fin cin
#define fout cout

using namespace std;

//ifstream fin ("test.in");
//ofstream fout ("test.out");

int N, M;
bool G[NMAX + 1][NMAX + 1];
bool viz[NMAX + 1];
int val[NMAX + 1];

void DFS(int node){
    viz[node] = 1;

    for(int i = 1; i <= N; i++){
        if(!viz[i] && G[i][node]){
            ///exista muchia
            val[i] = (0 - val[node] + 2) % 2;
            DFS(i);
        }
        else if(!viz[i] && !G[i][node]){
            ///nu exista muchia
            val[i] = (1 - val[node] + 2) % 2;
            DFS(i);
        }
    }
}

/*
inline void reset(int v[], int dim){
    for(int i = 0; i <= dim; i++){
        v[i] = 0;
    }
}
*/

inline int bunaMuchie(int a, int b){
    if(G[a][b] && (val[a] + val[b]) % 2 == 0){
        return 1;
    }
    if(!G[a][b] && (val[a] + val[b]) % 2 == 1){
        return 1;
    }

    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    fin >> N;
    fin >> M;

    for(int i = 1; i <= M; i++){
        int a, b;
        fin >> a >> b;

        G[a][b] = 1;
        G[b][a] = 1;
    }

    val[1] = 0;
    DFS(1);

    int OK1 = 1;
    for(int i = 1; i <= N; i++){
        for(int j = i + 1; j <= N; j++){
            if(!bunaMuchie(i, j)){
                OK1 = 0;
            }
        }
    }


    for(int i = 1; i <= N; i++){
        viz[i] = 0;
        val[i] = 0;
    }

    val[1] = 1;
    DFS(1);

    int OK2 = 1;
    for(int i = 1; i <= N; i++){
        for(int j = i + 1; j <= N; j++){
            if(!bunaMuchie(i, j)){
                OK2 = 0;
            }
        }
    }

    if(OK1 || OK2){
        fout << "DA\n";
    }
    else {
        fout << "NE\n";
    }


    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15
• Subtask 7: 15 / 15
• Subtask 8: 15 / 15