Submission #741247

#	Time	Username	Problem	Language	Result	Execution time	Memory
741247		Pichon5	Logičari (COCI21_logicari)	C++17	0 / 110	177 ms	30944 KiB

Main

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <sstream>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define jumanji ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define F first
#define S second
#define int long long
#define vi vector<int>
#define ll long long
using namespace std;
const int tam=1e5+5;
vector<vi>G;
int A;
int B;
bool vis[tam];
//find two nodes inside a cycle
void dfs(int u,int p){
    vis[u]=true;
    for(auto v:G[u]){
        if(v==p)continue;
        if(vis[v]){
            A=u;
            B=v;
            return;
        }
        dfs(v,u);
    }
}
//dp on tree
int dp[tam][2][2][2][2];
int f(int nodo,int color, int cP,int cA, int cB, int p=0){
    int &ans=dp[nodo][color][cP][cA][cB];
    if(ans!=-1)return ans;
    if(nodo==A && color!=cA)return ans=1e9;
    if(nodo==B && color!=cB)return ans=1e9;
    if(nodo==B && cA && cP)return ans=1e9;

    bool ok=0;
    if(nodo==A && cB)ok=1;
    if(nodo==B && cA)ok=1;
    if(cP)ok=1;
    
    int sum=color;
    for(auto v:G[nodo]){
        if(v==p)continue;
        sum+=f(v,0,color,cA,cB,nodo);
    }
    ans=1e9;
    if(ok){
        ans=sum;
    }else{
        //solo tengo que pintar uno
        for(auto v:G[nodo]){
            if(v==p)continue;
            int curr=sum-f(v,0,color,cA,cB,nodo)+f(v,1,color,cA,cB,nodo);
            ans=min(ans,curr);
        }
    }
    return ans;
}
signed main(){
    jumanji
    memset(dp,-1,sizeof dp);
    int n,a,b;
    cin>>n;
    assert(n<=tam);
    G.assign(n+1,vi());
    vector<pair<int,int>>edges;
    for(int i=0;i<=n;i++){
        cin>>a>>b;
        G[a].pb(b);
        G[b].pb(a);
        edges.pb({a,b});
    }
    dfs(1,0);
    G.assign(n+1,vi());
    for(auto e:edges){
        if(e.F==A and e.S==B)continue;
        if(e.F==B and e.S==A)continue;
        G[e.F].pb(e.S);
        G[e.S].pb(e.F);
    }
    assert(A!=0 and B!=0);
    assert(A!=B);
    //ambos 1s
    int res=1e9;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            int curr=f(A,i,0,i,j);
            res=min(res,curr);
        }
    }
    // cout<<A<<" "<<B<<endl;
    if(res>=1e9){
        cout <<-1<<endl;
    }else{
        cout<<res<<endl;
    }
    return 0;
}  
//Guess i wont be comming to church on sunday

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