Submission #1094127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094127		nguyen31hoang08minh2003	Ronald (COCI17_ronald)	C++14	120 / 120	23 ms	3160 KiB

ronald

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

/*

    v[x] + v[y] = 1 + e[x][y] (mod 2) for every x, y

    e[x][y] = 1 if x and y were initially connected

    N               variables
    N * (N - 1) / 2 equations

    -------------------------------------------------

    It can be noticed that
        if (n - 1) following equations are chosen,
            all remaining equations should be able to be determined

            v[1]        + v[n] = 1 + e[1][n]        (mod 2)
            ...
            v[n - 2]    + v[n] = 1 + e[n - 1][n]    (mod 2)

        because
            for every 1 <= x < y < n then
                we have
                    v[x] + v[n] = 1 + e[x][n]
                    v[y] + v[n] = 1 + e[y][n]
                =>  v[x] + v[y] = 1 + e[x][n] + e[y][n]

            this means that,
                as long as all remaining equations are consistent with these (n - 1) chosen equations
                    any solutions of this systems of these (n - 1) equations can be chosen
                        as solutions of the complete system of n * (n - 1) / 2 equations
                            (it is obvious that the system of (n - 1) equations should have solutions;
                             this can be easily proved by substituting one variable and determine remaining variables and check consistency)

*/

constexpr int MAX_N = 1003;

int N, M;
bool e[MAX_N][MAX_N];

signed main() {

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
//    freopen("output.OUT", "w", stdout);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> M;

    if (N <= 2) {
        puts("DA");
        return 0;
    }

    for (int x, y, m = 0; m < M; ++m) {
        cin >> x >> y;
        e[x][y] = e[y][x] = true;
    }

    for (int x = 1, y; x <= N; ++x)
        for (y = x + 1; y < N; ++y)
            if (e[x][y] != (1 ^ e[x][N] ^ e[y][N])) {
                puts("NE");
                return 0;
            }

    puts("DA");

    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