#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
352 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
352 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
464 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
352 KB |
Output is correct |
| 4 |
Correct |
0 ms |
476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
352 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
352 KB |
Output is correct |
| 3 |
Correct |
0 ms |
352 KB |
Output is correct |
| 4 |
Correct |
1 ms |
352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
352 KB |
Output is correct |
| 2 |
Correct |
0 ms |
352 KB |
Output is correct |
| 3 |
Correct |
1 ms |
352 KB |
Output is correct |
| 4 |
Correct |
0 ms |
356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
740 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1380 KB |
Output is correct |
| 3 |
Correct |
3 ms |
860 KB |
Output is correct |
| 4 |
Correct |
2 ms |
872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
616 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1124 KB |
Output is correct |
| 3 |
Correct |
14 ms |
2664 KB |
Output is correct |
| 4 |
Correct |
23 ms |
3160 KB |
Output is correct |
