Submission #862254

#	Time	Username	Problem	Language	Result	Execution time	Memory
862254		AbdelmagedNour	Logičari (COCI21_logicari)	C++17	0 / 110	3 ms	9308 KiB

Main

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40
• Subtask 4: 0 / 50