Submission #1272468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272468		alphas	Logičari (COCI21_logicari)	C++20	10 / 110	210 ms	40420 KiB

Main

/* Burung ini cuma template
░░   ▄▀▀▀▄░░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
*/
 
#include<bits/stdc++.h>
#define mp make_pair
#define fs first
#define sc second
#define pb push_back
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mod 1000000007
#define INF 1e9
#define ALPHABET_SIZE 26
using namespace std;
 
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

vector<int> adj[100005];
int specialNode, root;
long long depe[100005][2][2][2][2];

// the param for DP: now, currentColor (0/1), parentColor (0/1), rootColor (0/1), specialNodeColor (0/1)
// transition:
// - if currentColor = 1 (black)
//   - if parentColor = 1 (black), all of the child should 0 (white)
//   - if parentColor = 0 (white), choose 1 child that should be black
// - if currentColor = 0 (white)
//   - if parentColor = 1 (black), all of the child should 0 (white)
//   - if parentColor = 0 (white), choose 1 child that should be black
// 
// root is special (its parentColor is the specialNodeColor):
// - if currentColor = 1 (black)
//   - if specialNodeColor = 1 (black), all of the child should 0 (white)
//   - if specialNodeColor = 0 (white), choose 1 child that should be black
// - if currentColor = 0 (white)
//   - if specialNodeColor = 1 (black), all of the child should 0 (white)
//   - if specialNodeColor = 0 (white), choose 1 child that should be black
// now == specialNode:
// - if currentColor different from colorSpecialNode, return IMPOSSIBLE
// - if currentColor = 1 (black), rootColor = 1, and parentColor = 1, then return IMPOSSIBLE (this special node sees 2 black)
long long dp(int now, int par, int currentColor, int parentColor, int rootColor, int specialNodeColor) {
    if(now == specialNode) {
        if(currentColor != specialNodeColor) {
            return INF;
        }
        if(rootColor == 1 && parentColor == 1) {
            return INF;
        }
    }

    long long &ret = depe[now][currentColor][parentColor][rootColor][specialNodeColor];
    if(ret != -1) return ret;

    // count the dp if all of his child is white, store it in whiteCost
    long long whiteCost[adj[now].size() + 1];
    long long total = 0;
    for(int i = 0; i < adj[now].size(); i++) {
        if(adj[now][i] == par || (now == root && adj[now][i] == specialNode) || (now == specialNode && adj[now][i] == root)) continue;
        whiteCost[i] = dp(adj[now][i], now, 0, currentColor, rootColor, specialNodeColor);
        // if(rootColor == 1 && specialNodeColor == 0 && now == 1) {
        //     cout << "now = " << now << " adj[now][i] = " << adj[now][i] << " rootColor = " << rootColor << " specialNodeColor = " << specialNodeColor << " whiteCost = " << whiteCost[i] << endl;
        // }
        total += whiteCost[i];
    }

    // if(now == specialNode) {
    //     cout << "SPECIAL NODE now = " << now << " currentColor = " << currentColor << " parentColor = " << parentColor << " rootColor = " << rootColor << " specialNodeColor = " << specialNodeColor << endl;
    // }

    if(parentColor == 1) {
        ret = total;
    } else {
        // if currentColor = 1 (black), parentColor = 0 (white), then we should choose 1 child that should be black
        // but if there is no child, we should return IMPOSSIBLE

        ret = INF;
        for(int i = 0; i < adj[now].size(); i++) {
            if(adj[now][i] == par || (now == root && adj[now][i] == specialNode) || (now == specialNode && adj[now][i] == root)) continue;
            int cost = 0;
            if(currentColor == 1) cost = 2;
            // exchange the color of the child[i] from white to black
            ret = min(ret, total - whiteCost[i] + dp(adj[now][i], now, 1, currentColor, rootColor, specialNodeColor) + cost);
        }
    }
    
    return ret;
}

bool vis[100005];
pair<int, int> specialEdge;
void findCycle(int now, int par) {
    for(auto nxt : adj[now]) {
        if(nxt == par) continue;
        if(vis[nxt]) {
            specialEdge = {now, nxt};
            return;
        }
        vis[nxt] = true;
        findCycle(nxt, now);
    }
}

int main(){
    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    // we should pick the special edge from the cycle
    // we should find the cycle first
    memset(vis, false, sizeof(vis));
    vis[1] = true;
    findCycle(1, -1);
    // specialEdge = {root, specialNode}
    specialNode = specialEdge.second;
    root = specialEdge.first;

    // cout << "specialEdge = " << specialEdge.first << " " << specialEdge.second << endl;
    
    // 4 case for the special edge (root, specialNode):
    // - both of them are black
    // - both of them are white
    // - root is black, specialNode is white
    // - root is white, specialNode is black
    memset(depe, -1, sizeof(depe));
    long long ans = INF;
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            int cost = 0;
            if(i == 1 && j == 1) {
                cost = 2;
            }

            ans = min(ans, dp(root, -1, i, j, i, j) + cost);
            // cout << "i = " << i << " j = " << j << " dp = " << dp(root, -1, i, j, i, j) + cost << endl;
        }
    }
    if(ans >= INF) {
        ans = -1;
    }
    cout << ans << endl;

}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40
• Subtask 4: 0 / 50