oj.uz

Submission #871284

# Submission time Handle Problem Language Result Execution time Memory
871284 2023-11-10T12:18:06 Z HossamHero7 Logičari (COCI21_logicari) C++14
10 / 110
 138 ms 34188 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 1e5 + 5;
int dp[N][2][2][3][3];
bool vis[N];
vector<int> adj[N];
int sp = -1;
int parsp = 0;
void dfs(int node,int par){
    vis[node] = 1;
    for(auto ch : adj[node]){
        if(ch == par) continue;
        if(vis[ch]){
            if(sp == -1) sp = node;
            else parsp = node;
            continue;
        }
        dfs(ch,node);
    }
}
int solve(int node,int par,int cnode,int cpar,int csp,int csppar){
    int &ret = dp[node][cnode][cpar][csp][csppar];
    if(~ret) return ret;
    if(node == sp){
        assert(cnode == csp);
        if(cpar && csppar) return ret = 1e9;
        if(cpar || csppar){
            ret = 0;
            for(auto ch : adj[node]){
                if(ch == par || ch == parsp) continue;
                ret += solve(ch,node,0,cnode,csp,csppar);
            }
            return ret;
        }
        else {
            ret = 0;
            int mn = 1e9;
            for(auto ch : adj[node]){
                if(ch == par || ch == parsp) continue;
                ret += solve(ch,node,0,cnode,csp,csppar);
                mn = min(mn , solve(ch,node,1,cnode,csp,csppar) + 1 - solve(ch,node,0,cnode,csp,csppar));
            }
            ret += mn;
            return ret;
        }
    }
    else {
        ret = 1e9;
        bool b = 0;
        for(auto ch : adj[node]){
            if(ch == par) continue;
            if(ch == sp) b = 1;
        }
        if(b){
            if(csp == 2){
                if(cpar){
                    ret = 0;
                    for(auto ch : adj[node]){
                        if(ch == sp || ch == par) continue;
                        ret += solve(ch,node,0,cnode,0,cnode);
                    }
                    return ret;
                }
                else {
                    int c1 = 1;
                    for(auto ch : adj[node]){
                        if(ch == sp || ch == par) continue;
                        c1 += solve(ch,node,0,cnode,1,cnode);
                    }
                    int mn = 1e9;
                    ret = 0;
                    for(auto ch : adj[node]){
                        if(ch == par || ch == sp) continue;
                        mn = min(mn , solve(ch,node,1,cnode,0,cnode)+1 - solve(ch,node,0,cnode,0,cnode));
                        ret += solve(ch,node,0,cnode,0,cnode);
                    }
                    ret += mn;
                    ret = min(ret , c1);
                    return ret;
                }
            }
            else {
                if(csp && cpar) return ret = 1e9;
                if(csp){
                    ret = 0;
                    for(auto ch : adj[node]){
                        if(ch == par) continue;
                        ret += solve(ch,node,(ch==sp?csp:0),cnode,csp,csppar);
                    }
                    return ret;
                }
                else {
                    int mn = 1e9;
                    ret = 0;
                    for(auto ch : adj[node]){
                        if(ch == par) continue;
                        if(ch == sp) ret += solve(ch,node,csp,cnode,csp,csppar);
                        else {
                            ret += solve(ch,node,0,cnode,csp,csppar);
                            mn = min(mn , solve(ch,node,1,cnode,csp,csppar)+1 - solve(ch,node,0,cnode,csp,csppar));
                        }
                    }
                    if(!cpar) ret += mn;
                    return ret;
                }
            }
        }
        else {
            if(cpar){
                ret = 0;
                for(auto ch : adj[node]){
                    if(ch == par) continue;
                    ret += solve(ch,node,0,cnode,csp,csppar);
                }
                return ret;
            }
            else {
                int mn = 1e9;
                ret = 0;
                for(auto ch : adj[node]){
                    if(ch == par) continue;
                    mn = min(mn , solve(ch,node,1,cnode,csp,csppar)+1 - solve(ch,node,0,cnode,csp,csppar));
                    ret += solve(ch,node,0,cnode,csp,csppar);
                }
                ret += mn;
                return ret;
            }
        }
    }
}
void solve(){
    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);
    }
    dfs(1,0);
    memset(dp,-1,sizeof(dp));
    int ans = min(solve(1,0,0,0,2,2),solve(1,0,1,0,2,2)+1);
    if(ans >= 1e9) cout<<-1<<endl;
    else cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16728 KB Output is correct
5 Correct 138 ms 34012 KB Output is correct
6 Correct 135 ms 34136 KB Output is correct
7 Correct 136 ms 34188 KB Output is correct
8 Correct 134 ms 34020 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 16984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 16984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16728 KB Output is correct
5 Correct 138 ms 34012 KB Output is correct
6 Correct 135 ms 34136 KB Output is correct
7 Correct 136 ms 34188 KB Output is correct
8 Correct 134 ms 34020 KB Output is correct
9 Incorrect 4 ms 16984 KB Output isn't correct
10 Halted 0 ms 0 KB -