oj.uz

Submission #659806

# Submission time Handle Problem Language Result Execution time Memory
659806 2022-11-19T09:43:38 Z Neacsu_Mihai Ronald (COCI17_ronald) C++14
120 / 120
 31 ms 1328 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 8 ms 816 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 8 ms 824 KB Output is correct
3 Correct 25 ms 1312 KB Output is correct
4 Correct 31 ms 1328 KB Output is correct