Submission #988161

#	Time	Username	Problem	Language	Result	Execution time	Memory
988161		0pt1mus23	Logičari (COCI21_logicari)	C++14	110 / 110	216 ms	170128 KiB

Main

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define ins insert
#define pb push_back
#define int unsigned long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl;return;
#define reach cerr << "reached >.<!" << endl;
/*
    m : 11059739 -> l ~23
    p : 4567896467
*/
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7, sze = 1e6 + 50, inf = 1e6, prime = 2333;

//\\
dp / binary search / greedy / sprase table / segment tree 
//

int root,specialnode,n;
int dp[sze][2][2][2][2];
int p[sze];
int dsu[sze];
vector<int> graph[sze];

int f(int node){
    if(dsu[node]==node){
        return node;
    }
    return dsu[node]=f(dsu[node]);
}


void dfs(int node,int par=0){
    p[node]=par;
    for(auto v:graph[node]){
        if(v!=par){
            dfs(v,node);
        }
    }
}

int kafkef(int node,int me,int pc,int rt,int sp){
    if(dp[node][me][pc][rt][sp]!=-1){
        return dp[node][me][pc][rt][sp];
    }
    if( (node==root && me!=rt) | (node==specialnode&& me!=sp) | (node==specialnode && pc && rt) ){
        return dp[node][me][pc][rt][sp] = inf;
    }
    int ans=inf;

    bool mustwhite = ( pc | (node == root && sp) | (node == specialnode && rt));

    int sum=me;
    for(auto v:graph[node]){
        if(v!=p[node]){
            sum+=kafkef(v,0,me,rt,sp);
        }
    }

    if(mustwhite){
        ans=min(ans,sum);
    }
    else{
        for(auto v:graph[node]){
            if(v!=p[node]){
                ans=min(ans, sum - kafkef(v,0,me,rt,sp)  + kafkef(v,1,me,rt,sp));
            }
        }
    }


    return dp[node][me][pc][rt][sp]=ans;

}

void gkd(){
    memset(dp, -1, sizeof dp);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        dsu[i]=i;
    }
    for(int i=0;i<n;i++){
        int u,v;
        cin>>u>>v;
        int x = f(u);
        int y = f(v);
        if(x==y){
            root=u;
            specialnode=v;
        }
        else{
            dsu[x]=y;
            graph[u].pb(v);
            graph[v].pb(u);
        }
    }
    dfs(root);
    
    int ans=inf;

    for(int i =0 ;i<=1;i++){
        for(int j=0;j<=1;j++){
            ans=min(ans,kafkef(root,i,0,i,j));
        }
    }

    if(ans>=inf){
        drop(-1);
    }
    drop(ans);

}


signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1; //cin>>tt;
    while (tt--)gkd();
}

Compilation message (stderr)

Main.cpp:19:1: warning: multi-line comment [-Wcomment]
   19 | //\\
      | ^
Main.cpp: In function 'long long unsigned int kafkef(long long unsigned int, long long unsigned int, long long unsigned int, long long unsigned int, long long unsigned int)':
Main.cpp:47:32: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   47 |     if(dp[node][me][pc][rt][sp]!=-1){
      |        ~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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