oj.uz

답안 #503432

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503432 2022-01-08T00:06:30 Z joshualiu555 Ronald (COCI17_ronald) C++17
120 / 120
 37 ms 10112 KB 
/*
  _____                                     _        _
 / ____|                                   | |      | |
| |  __ _ __ __ _ ___ ___ _   _ _ __   ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
 \_____|_|  \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
                           __/ | |
                          |___/|_|
*/

#pragma gcc target ("avx2")
#pragma gcc optimization ("O3")
#pragma gcc optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using segset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, x, n) for (int i = x; i <= n; i++)
#define F0R(i, x, n) for (int i = x; i >= n; i--)
#define TRAV(it, x) for (auto it = x.begin(); it != x.end(); it++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define sz size
#define pob pop_back
#define pb push_back
#define ins insert
#define mp make_pair
#define rz resize
#define rev reverse
#define lb lower_bound
#define ub upper_bound
// fill for 1
// 0x3f3f3f3f for 1e9
#define mem(a, x) memset(a, x, sizeof(a))
#define HEX 0x3f3f3f3f

using ll = long long;
const int INF = 2e5 + 5;
const int MOD = 1e9 + 7;
// DLRU
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, -1, 1, 0};

/*
 *
*/

//

int n, m, adj[1005][1005];
int mat[1005][1005];

void flip(int x, int y) {
    FOR(i, 0, n - 1) mat[i][x] ^= 1;
    FOR(i, 0, n - 1) mat[y][i] ^= 1;
}

bool solve() {
    FOR(i, 0, n - 1) {
        FOR(j, 0, n - 1) {
            mat[i][j] = adj[i][j];
        }
    }

    int bit = mat[0][0];
    FOR(i, 1, n - 1) {
        if (mat[i][0] == mat[0][i] && mat[i][0] == bit) flip(i, i);
        else if (mat[i][0] != mat[0][i]) {
            if (mat[i][0] == bit) flip(i, i + 1);
            else flip(i + 1, i);
        }
    }

    FOR(i, 1, n - 1) {
        FOR(j, 1, n - 1) {
            if (mat[i][j] != bit) return false;
        }
    }

    return true;
}

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

//    ifstream cin(".in");
//    ofstream cout(".out");

//    int t;
//    cin >> t;
//    while (t--) {
//        solve();
//    }

    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a][b] = true;
        adj[b][a] = true;
    }

    FOR(i, 0, n - 1) adj[i][i] = true;

    if (solve()) {
        cout << "DA\n";
        return 0;
    }
    FOR(i, 0, n - 1) {
        FOR(j, 0, n - 1) {
            adj[i][j] ^= 1;
        }
    }
    if (solve()) {
        cout << "DA\n";
        return 0;
    }
    cout << "NE\n";

    return 0;
}

/*
I want to do O(N^2), but there are too many edges (<= 500,000) because it is a complete graph
However, the space complexity can be O(N^2), so you can have an adjancency matrix

The last move must be a completely isolated node where every other node is completely connected.
That node's entire row will be false except for itself

This reduces the problem to (Similar to Lights Out):
You have a grid of size N * N with 1's and 0's
In one operation, you can choose any indices i, j where i = j
and flip the entire row and entire column (grid[i][j] stays the same since it's flipped twice)
Can you make the entire grid full of 1's?

You want the last flip to be a 1 cell
where its entire row and column are 0

Since XOR is associative, it doesn't matter what order
you choose
You also don't need to find the optimal answer
so just fix the last flip as the top left corder

XOR is also communiative, so if you were finding the
optimal answer, never choose the same cell twice

Let's just work backwards from the complete graph
For each cell in the top row or left column
excluding cell(0, 0)
Must be the same indices, so
simultaneously check
grid[0][i] and grid[i][0]
If they are both equal, either move on or flip the cell between
them (depending on which of the 2 states you are checking)
If they are different, just flip the correct cell somewhere
after these two

If at the end, every other cell not in the left column or top row
is 1, answer is DA
otherwise NE

*/

//

Compilation message

ronald.cpp:12: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
   12 | #pragma gcc target ("avx2")
      | 
ronald.cpp:13: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   13 | #pragma gcc optimization ("O3")
      | 
ronald.cpp:14: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   14 | #pragma gcc optimization ("unroll-loops")
      |

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 308 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 332 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 1 ms 460 KB Output is correct

Subtask #5
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 684 KB Output is correct

Subtask #6
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 1 ms 912 KB Output is correct
3 Correct 1 ms 1088 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 16 ms 4660 KB Output is correct
3 Correct 4 ms 2764 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct

Subtask #8
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1860 KB Output is correct
2 Correct 8 ms 4524 KB Output is correct
3 Correct 27 ms 9456 KB Output is correct
4 Correct 37 ms 10112 KB Output is correct