oj.uz

Submission #863467

# Submission time Handle Problem Language Result Execution time Memory
863467 2023-10-20T12:00:03 Z 3omar_ahmed Logičari (COCI21_logicari) C++17
10 / 110
 1000 ms 31248 KB 
#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
const int N = 1e5 + 5;

int n;
int dp[N][2][2][2][2];
vector < vector < int >> adj;
pair < int , int > extra = {-1, -1};

struct DSU {
    vector < int > par, sz;

    void init(int n) {
        par = sz = vector < int > (n + 1);
        for(int i = 1 ; i <= n ; i++) {
            par[i] = i, sz[i] = 1;
        }
    }
    
    int find(int node) {
        if(par[node] == node) return node;
        return par[node] = find(par[node]);
    }

    int join(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return 0;
        if(sz[v] > sz[u]) {
            swap(u, v);
        }
        sz[u] += sz[v];
        par[v] = u;
        return 1;
    }
};


int solve(int node, int par, int color_par, int color_node, int color_extra1, int color_extra2) {
    auto ret = dp[node][color_par][color_node][color_extra1][color_extra2];
    if(ret != -1) {
        return ret;
    }

    int counter = color_par;
    for(auto child : adj[node]) {
        if(child == par) continue;
        if(child == extra.first) {
            counter += color_extra1;
        } else if(child == extra.second) {
            counter += color_extra2;
        }
    }

    if(node == extra.first) counter += color_extra2;
    else if(node == extra.second) counter += color_extra1;

    if(counter >= 2) {
        return ret = 1e9;
    } else if(counter == 1) {
        int ans = 0;
        for(auto child : adj[node]) {
            if(child == par) continue;
            if(child == extra.first) {
                ans += solve(child, node, color_node, color_extra1, color_extra1, color_extra2);
            } else if(child == extra.second) {
                ans += solve(child, node, color_node, color_extra2, color_extra1, color_extra2);
            } else {
                ans += solve(child, node, color_node, 0, color_extra1, color_extra2); 
            }
        }
        return ret = ans;
    } else {
        int ans = 0, mx = -1e16;
        for(auto child : adj[node]) {
            if(child == par) continue;
            if(child == extra.first) {
                ans += solve(child, node, color_node, color_extra1, color_extra1, color_extra2);
            } else if(child == extra.second) {
                ans += solve(child, node, color_node, color_extra2, color_extra1, color_extra2);
            } else {
                int b = solve(child, node, color_node, 1, color_extra1, color_extra2) + 1; 
                int a = solve(child, node, color_node, 0, color_extra1, color_extra2);
                ans += a, mx = max(mx, a - b);
            }
        }
        if(mx < -1e15) return ret = 1e9;
        return ret = ans - mx;
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    cin >> n;

    DSU s; s.init(n);
    adj = vector < vector < int >> (n + 1);
    
    for(int i = 0 ; i < n ; i++) {
        int u, v;
        cin >> u >> v;
        if(!s.join(u, v)) {
            extra = {u, v};
        }
        adj[u].push_back(v);
        adj[v].push_back(u);
    }    

    for(int i = 0 ; i < adj[extra.first].size() ; i++) {
        if(adj[extra.first][i] == extra.second) {
            adj[extra.first].erase(adj[extra.first].begin() + i);
            break;
        }
    }

    for(int i = 0 ; i < adj[extra.second].size() ; i++) {
        if(adj[extra.second][i] == extra.first) {
            adj[extra.second].erase(adj[extra.second].begin() + i);
            break;
        }
    }

    cerr << extra.first << " " << extra.second << endl;

    int ans = 1e9;

    memset(dp, -1, sizeof(dp));
    
    if(extra.first == 1) {
        int a = solve(1, 1, 0, 0, 0, 0);
        int b = solve(1, 1, 0, 1, 1, 0) + 1;
        int c = solve(1, 1, 0, 0, 0, 1) + 1;
        int d = solve(1, 1, 0, 1, 1, 1) + 2;

        ans = min({a, b, c, d});
    } else if(extra.second == 1) {
        int a = solve(1, 1, 0, 0, 0, 0);
        int b = solve(1, 1, 0, 0, 1, 0) + 1;
        int c = solve(1, 1, 0, 1, 0, 1) + 1;
        int d = solve(1, 1, 0, 1, 1, 1) + 2;

        ans = min({a, b, c, d});
    } else {
        int a = solve(1, 1, 0, 0, 0, 0);
        int b = solve(1, 1, 0, 0, 1, 0) + 1;
        int c = solve(1, 1, 0, 0, 0, 1) + 1;
        int d = solve(1, 1, 0, 0, 1, 1) + 2;

        int e = solve(1, 1, 0, 1, 0, 0) + 1;
        int f = solve(1, 1, 0, 1, 1, 0) + 2;
        int g = solve(1, 1, 0, 1, 0, 1) + 2;
        int h = solve(1, 1, 0, 1, 1, 1) + 3;
        
        ans = min({a, b, c, d, e, f, g, h});
    }

    if(ans > 1e7) ans = -1;
    cout << ans << endl;
    return 0 ;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:113:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(int i = 0 ; i < adj[extra.first].size() ; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:120:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i = 0 ; i < adj[extra.second].size() ; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12888 KB Output is correct
5 Execution timed out 1097 ms 31248 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 2 ms 13044 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 2 ms 13144 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12888 KB Output is correct
12 Correct 2 ms 12952 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 2 ms 13044 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 2 ms 13144 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12888 KB Output is correct
12 Correct 2 ms 12952 KB Output is correct
13 Execution timed out 1088 ms 12892 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12888 KB Output is correct
5 Execution timed out 1097 ms 31248 KB Time limit exceeded
6 Halted 0 ms 0 KB -