제출 #741261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
741261		Pichon5	Logičari (COCI21_logicari)	C++17	110 / 110	253 ms	33180 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;
 
vector<vi>G;
vi vis;
//fin endpoints of one edge in a cycle of an undirected graph
int A,B;
const int tam=1e5+100;
const int INF=1e9;
int dp[tam][2][2][2][2];
void dfs(int u,int p){
    vis[u]=1;
    for(auto v:G[u]){
        if(v==p)continue;
        if(vis[v]==1){
            A=u;
            B=v;
            return;
        }
        if(vis[v]==0){
            dfs(v,u);
            if(A!=-1)return;
        }
    }
    vis[u]=2;
}
int f(int nodo, int c,int cP, int cA, int cB, int padre){
    if(dp[nodo][c][cP][cA][cB] != -1) return dp[nodo][c][cP][cA][cB];
    if(nodo==A && c!=cA)return dp[nodo][c][cP][cA][cB]=INF;
    if(nodo==B && c!=cB)return dp[nodo][c][cP][cA][cB]=INF;
    if(nodo==B && cA && cP)return dp[nodo][c][cP][cA][cB]=INF;
    bool ok=0;
    if(cP)ok=1;
    if(nodo==A && cB)ok=1;
    if(nodo==B && cA)ok=1;
    int sum=c;
    for(auto v:G[nodo]){
        if(v==padre)continue;
        sum+=f(v,0,c,cA,cB,nodo);
    }
    dp[nodo][c][cP][cA][cB]=INF;
    if(ok){
        dp[nodo][c][cP][cA][cB]=sum;
    }else{
        for(auto v:G[nodo]){
            if(v==padre)continue;
            dp[nodo][c][cP][cA][cB]=min(dp[nodo][c][cP][cA][cB],sum-f(v,0,c,cA,cB,nodo)+f(v,1,c,cA,cB,nodo));
        }
    }
    return dp[nodo][c][cP][cA][cB];
}
signed main(){
    memset(dp,-1,sizeof dp);
    int n,a,b;
    cin>>n;
    vector<pair<int,int>>edges;
    G.resize(n+1);
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        G[a].pb(b);
        G[b].pb(a);
        edges.pb({a,b});
    }
    vis.assign(n+1,0);
    A=-1;
    B=-1;
    dfs(1,-1);
    G.clear();
    G.resize(n+1);
    for(auto e:edges){
        if(e.F==A && e.S==B)continue;
        if(e.F==B && e.S==A)continue;
        G[e.F].pb(e.S);
        G[e.S].pb(e.F);
    }
    ll res=INF;
    res=min(res,f(A,0,0,0,0,-1));
    res=min(res,f(A,0,0,0,1,-1));
    res=min(res,f(A,1,0,1,0,-1));
    res=min(res,f(A,1,0,1,1,-1));
    if(res>=INF)cout<<-1<<endl;
    else cout<<res<<endl;
 
 
 
 
    return 0;
}  
//Guess i wont be comming to church on sunday

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