Submission #503432

#	Time	Username	Problem	Language	Result	Execution time	Memory
503432		joshualiu555	Ronald (COCI17_ronald)	C++17	120 / 120	37 ms	10112 KiB

ronald

/*
  _____                                     _        _
 / ____|                                   | |      | |
| |  __ _ __ __ _ ___ ___ _   _ _ __   ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
 \_____|_|  \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
                           __/ | |
                          |___/|_|
*/

#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 (stderr)

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 / 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