oj.uz

답안 #862254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862254 2023-10-17T21:03:24 Z AbdelmagedNour Logičari (COCI21_logicari) C++17
0 / 110
 3 ms 9308 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const int N=100005,INF=1e9;
struct DSU{
    int p[N],sz[N];
    void init(int n){
        iota(p,p+n+1,0);
        fill(sz,sz+n+1,1);
    }
    int Find(int u){
        return (p[u]==u?u:p[u]=Find(p[u]));
    }
    bool operator()(int u,int v){
        u=Find(u);v=Find(v);
        if(u==v)return 0;
        if(sz[u]>sz[v])swap(u,v);
        sz[v]+=sz[u];
        p[u]=v;
        return 1;
    }
}dsu;
int n,root,special;
int dp[N][2][2][2][2];//cur,root,par,special
int p[N];
vector<vector<int>>adj(N);
void dfs(int v,int par){
    p[v]=par;
    for(auto u:adj[v]) {
        if(u==par)continue;
        dfs(u,v);
    }
}
int solve(int v,int cur,int par,int rot,int sp){
	int&ret=dp[v][cur][par][root][sp];
    if(~ret)return ret;
    ret=INF;
    bool flag=1;
    if(v==root&&cur!=rot)flag=0;
    if(v==special&&cur!=sp)flag=0;
    if(v==special&&par&&rot)flag=0;
    if(!flag)return ret;
	
    bool covered=0;
    if(par)covered=1;
    if(v==root&&sp)covered=1;
    if(v==special&&rot)covered=1;
    ll sum=cur;
    for(auto u:adj[v]){
        if(u==p[v])continue;
        sum+=solve(u,0,cur,rot,sp);
    }
    if(covered){
        ret=min(ll(ret),sum);
    }else{
        for(auto u:adj[v]){
            if(u==p[v])continue;
            ll val=sum-solve(u,0,cur,rot,sp)+solve(u,1,cur,rot,sp);
            ret=min(ll(ret), val);
        }
    }
    return ret;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(dp,-1,sizeof(dp));
    cin>>n;
    dsu.init(n);
    for(int i=0;i<n;i++){
        int u,v;
        cin>>u>>v;		
        if(!dsu(u,v)){
            root=u;
            special=v;
        }else{
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }
	dfs(root,0);
	int res=INF;
	for(auto rot:{0,1})for(auto sp:{0,1})res=min(res,solve(root,rot,0,rot,sp));
	cout<<(res==INF?-1:res);
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 40.0

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

Subtask #4
0 / 50.0

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