oj.uz

Submission #582718

# Submission time Handle Problem Language Result Execution time Memory
582718 2022-06-24T10:40:42 Z dxz05 Logičari (COCI21_logicari) C++14
20 / 110
 1000 ms 11720 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);
    }

    if (n <= 20) {
        cout << stress(g) << endl;
    } else {
        cout << logicari(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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 47 ms 11596 KB Output is correct
6 Correct 42 ms 11596 KB Output is correct
7 Correct 52 ms 11720 KB Output is correct
8 Correct 40 ms 11656 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 304 KB Output is correct
2 Correct 170 ms 304 KB Output is correct
3 Correct 190 ms 332 KB Output is correct
4 Correct 177 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 76 ms 304 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 36 ms 212 KB Output is correct
9 Correct 180 ms 304 KB Output is correct
10 Correct 166 ms 212 KB Output is correct
11 Correct 22 ms 212 KB Output is correct
12 Correct 155 ms 304 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 304 KB Output is correct
2 Correct 170 ms 304 KB Output is correct
3 Correct 190 ms 332 KB Output is correct
4 Correct 177 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 76 ms 304 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 36 ms 212 KB Output is correct
9 Correct 180 ms 304 KB Output is correct
10 Correct 166 ms 212 KB Output is correct
11 Correct 22 ms 212 KB Output is correct
12 Correct 155 ms 304 KB Output is correct
13 Execution timed out 1045 ms 340 KB Time limit exceeded
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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 47 ms 11596 KB Output is correct
6 Correct 42 ms 11596 KB Output is correct
7 Correct 52 ms 11720 KB Output is correct
8 Correct 40 ms 11656 KB Output is correct
9 Correct 161 ms 304 KB Output is correct
10 Correct 170 ms 304 KB Output is correct
11 Correct 190 ms 332 KB Output is correct
12 Correct 177 ms 308 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 76 ms 304 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 36 ms 212 KB Output is correct
17 Correct 180 ms 304 KB Output is correct
18 Correct 166 ms 212 KB Output is correct
19 Correct 22 ms 212 KB Output is correct
20 Correct 155 ms 304 KB Output is correct
21 Execution timed out 1045 ms 340 KB Time limit exceeded
22 Halted 0 ms 0 KB -