oj.uz

답안 #741251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
741251 2023-05-13T23:53:14 Z Pichon5 Logičari (COCI21_logicari) C++17
0 / 110
 227 ms 33136 KB 
#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=0;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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Correct 5 ms 12756 KB Output is correct
4 Correct 5 ms 12756 KB Output is correct
5 Incorrect 227 ms 33136 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Incorrect 5 ms 12756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Incorrect 5 ms 12756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Correct 5 ms 12756 KB Output is correct
4 Correct 5 ms 12756 KB Output is correct
5 Incorrect 227 ms 33136 KB Output isn't correct
6 Halted 0 ms 0 KB -