oj.uz

Submission #582717

# Submission time Handle Problem Language Result Execution time Memory
582717 2022-06-24T10:40:12 Z dxz05 Logičari (COCI21_logicari) C++14
10 / 110
 190 ms 11232 KB 
#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

#include <random>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define lla(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

#define MP make_pair

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.000001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e6 + 3e2;
const int M = 1111;

int stress(vector<vector<int>> g){
    int n = g.size();
    int ans = -1;
    for (int mask = 0; mask < (1 << n); mask++){
        vector<bool> flag(n);
        for (int i = 0; i < n; i++) flag[i] = mask & (1 << i);

        bool ok = true;
        for (int i = 0; i < n; i++){
            int cnt = 0;
            for (int j : g[i]) cnt += flag[j];

            if (cnt != 1) ok = false;
        }

        if (ok){
            if (ans == -1) ans = bpc(mask); else
                ans = min(ans, bpc(mask));
        }

    }

    return ans;
}

int logicari(vector<vector<int>> g){
    int n = g.size();
    vector<int> color(n, -1);

    bool ok = false;
    for (int i = 0; i < n; i++){
        if (g[i].size() == 1){
            color[g[i][0]] = 1;
            ok = true;
        }
    }

    if (!ok) return (n % 4 == 0 ? n / 2 : -1);

    for (int it = 1; it <= (n + 5) * (n + 5); it++){
        for (int i = 0; i < n; i++){
            int black = 0, white = 0;
            for (int j : g[i]){
                if (color[j] == 0) white++;
                if (color[j] == 1) black++;
            }

            int sz = (int)g[i].size();

            if (black == 1){
                for (int j : g[i]){
                    if (color[j] == -1) color[j] = 0;
                }
            } else if (white == sz - 1){
                for (int j : g[i]){
                    if (color[j] == -1) color[j] = 1;
                }
            }

        }

    }

    for (int i = 0; i < n; i++) cout << color[i] << ' '; cout << endl;

    for (int i = 0; i < n; i++){
        if (color[i] == -1) return -1;
    }

    int ans = 0;
    for (int i = 0; i < n; i++){
        ans += color[i];

        int cnt = 0;
        for (int j : g[i]) cnt += color[j] == 1;

        if (cnt != 1) return -1;
    }

    return ans;
}

void solve(int TC) {
    int n;
    cin >> n;

    vector<vector<int>> g(n);
    for (int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        --x, --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    cout << stress(g) << endl;

}

int main() {
    startTime = clock();
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int TC = 1;
//    cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

#ifdef dddxxz
    cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

Main.cpp: In function 'int logicari(std::vector<std::vector<int> >)':
Main.cpp:110:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  110 |     for (int i = 0; i < n; i++) cout << color[i] << ' '; cout << endl;
      |     ^~~
Main.cpp:110:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  110 |     for (int i = 0; i < n; i++) cout << color[i] << ' '; cout << endl;
      |                                                          ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 55 ms 11232 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 308 KB Output is correct
2 Correct 161 ms 316 KB Output is correct
3 Correct 190 ms 304 KB Output is correct
4 Correct 178 ms 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 74 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 42 ms 320 KB Output is correct
9 Correct 181 ms 308 KB Output is correct
10 Correct 184 ms 308 KB Output is correct
11 Correct 23 ms 212 KB Output is correct
12 Correct 168 ms 304 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 308 KB Output is correct
2 Correct 161 ms 316 KB Output is correct
3 Correct 190 ms 304 KB Output is correct
4 Correct 178 ms 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 74 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 42 ms 320 KB Output is correct
9 Correct 181 ms 308 KB Output is correct
10 Correct 184 ms 308 KB Output is correct
11 Correct 23 ms 212 KB Output is correct
12 Correct 168 ms 304 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 55 ms 11232 KB Output isn't correct
6 Halted 0 ms 0 KB -