Submission #862505

#	Time	Username	Problem	Language	Result	Execution time	Memory
862505		Ahmed57	Logičari (COCI21_logicari)	C++17	110 / 110	119 ms	35988 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long dp[100001][2][2];
bool ss = 0;
vector<int> cyc;stack<int> st;int be[100001];
vector<int> adj[100001];
bool lol[100001];
void getcyc(int i,int pr){
    if(be[i]){
        cyc.push_back(i);
        lol[i] = 1;
        while(st.top()!=i){
            cyc.push_back(st.top());
            lol[st.top()] = 1;
            st.pop();
        }
        ss = 1;return ;
    }
    be[i] = 1;st.push(i);
    for(auto j:adj[i]){
        if(j!=pr)getcyc(j,i);
        if(ss)return ;
    }
    be[i] = 0;st.pop();
}
int solve(int i,int pr,int par,int sh){
    if(dp[i][par][sh]!=-1)return dp[i][par][sh];
    if(par==1){
        if(sh==1){
            long long c1 = 0;
            for(auto j:adj[i]){
                if(lol[j]||j==pr)continue;
                c1+=solve(j,i,1,0);
            }
            return dp[i][par][sh] = min(c1+sh,1000000000ll);
        }else{
            long long c1 = 0;
            for(auto j:adj[i]){
                if(lol[j]||j==pr)continue;
                c1+=solve(j,i,0,0);
            }
            return dp[i][par][sh] = min(c1+sh,1000000000ll);
        }
    }else{
        if(sh==1){
            long long c1 = 0;
            for(auto j:adj[i]){
                if(lol[j]||j==pr)continue;
                c1+=solve(j,i,1,0);
            }
            long long ans = 1e9;
            for(auto j:adj[i]){
            if(lol[j]||j==pr)continue;
                ans = min(ans,c1-solve(j,i,1,0)+solve(j,i,1,1));
            }
            return dp[i][par][sh] = ans+sh;
        }else{
            long long c1 = 0;
            for(auto j:adj[i]){
                if(lol[j]||j==pr)continue;
                c1+=solve(j,i,0,0);
            }
            long long ans = 1e9;
            for(auto j:adj[i]){
                if(lol[j]||j==pr)continue;
                ans = min(ans,c1-solve(j,i,0,0)+solve(j,i,0,1));
            }
            return dp[i][par][sh] = ans+sh;
        }
    }
}
long long dp2[100001][2][2][2][2];
int solve2(int i,int la,int sh,int fi,int shla){
    if(dp2[i][la][sh][fi][shla]!=-1)return dp2[i][la][sh][fi][shla];
    if(i==0){
        int c1 = min(1000000000,solve2(i+1,0,0,0,1)+solve(cyc[i],0,1,0));
        c1 = min(c1,solve2(i+1,0,1,0,0)+solve(cyc[i],0,1,0));
        c1 = min(c1,solve2(i+1,0,0,0,0)+solve(cyc[i],0,0,0));
        c1 = min(c1,solve2(i+1,1,0,1,1)+solve(cyc[i],0,1,1));
        c1 = min(c1,solve2(i+1,1,1,1,0)+solve(cyc[i],0,1,1));
        c1 = min(c1,solve2(i+1,1,0,1,0)+solve(cyc[i],0,0,1));
        return dp2[i][la][sh][fi][shla] = c1;
    }else if(i<cyc.size()-1){
        int c1 = 1e9;
        if(la==0){
            if(sh==0){
                c1 = min(c1,solve(cyc[i],0,0,0)+solve2(i+1,0,0,fi,shla));
                c1 = min(c1,solve(cyc[i],0,1,0)+solve2(i+1,0,1,fi,shla));
                return dp2[i][la][sh][fi][shla] = c1;
            }else{
                c1 = min(c1,solve(cyc[i],0,0,1)+solve2(i+1,1,0,fi,shla));
                c1 = min(c1,solve(cyc[i],0,1,1)+solve2(i+1,1,1,fi,shla));
                return dp2[i][la][sh][fi][shla] = c1;
            }
        }else{
            if(sh==0){
                c1 = min(c1,solve(cyc[i],0,1,0)+solve2(i+1,0,0,fi,shla));
                return dp2[i][la][sh][fi][shla] = c1;
            }else{
                c1 = min(c1,solve(cyc[i],0,1,1)+solve2(i+1,1,0,fi,shla));
                return dp2[i][la][sh][fi][shla] = c1;
            }
        }
    }else{
        if(sh!=shla||(fi&&la)){
            return dp2[i][la][sh][fi][shla] = 1e9;
        }else{
            return dp2[i][la][sh][fi][shla] = solve(cyc[i],0,(fi||la),sh);
        }
    }
}
int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    getcyc(1,0);
    memset(dp,-1,sizeof dp);
    memset(dp2,-1,sizeof dp2);
    cout<<(solve2(0,0,0,0,0)>=1e9?-1:solve2(0,0,0,0,0))<<endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int solve2(int, int, int, int, int)':
Main.cpp:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     }else if(i<cyc.size()-1){
      |              ~^~~~~~~~~~~~~

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