oj.uz

Submission #871299

# Submission time Handle Problem Language Result Execution time Memory
871299 2023-11-10T13:44:45 Z HossamHero7 Logičari (COCI21_logicari) C++14
110 / 110
 189 ms 46712 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
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);
    }
}
ll solve(int node,int par,int cnode,int cpar,int csp,int csppar){
    ll &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));
    ll 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;
}
signed 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 5 ms 31064 KB Output is correct
2 Correct 5 ms 31068 KB Output is correct
3 Correct 4 ms 31068 KB Output is correct
4 Correct 5 ms 30868 KB Output is correct
5 Correct 189 ms 46560 KB Output is correct
6 Correct 181 ms 46708 KB Output is correct
7 Correct 172 ms 46712 KB Output is correct
8 Correct 167 ms 46708 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31064 KB Output is correct
2 Correct 5 ms 31068 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 6 ms 31068 KB Output is correct
5 Correct 4 ms 31068 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 5 ms 31068 KB Output is correct
8 Correct 5 ms 30848 KB Output is correct
9 Correct 5 ms 31064 KB Output is correct
10 Correct 5 ms 31068 KB Output is correct
11 Correct 5 ms 31068 KB Output is correct
12 Correct 5 ms 31068 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31064 KB Output is correct
2 Correct 5 ms 31068 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 6 ms 31068 KB Output is correct
5 Correct 4 ms 31068 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 5 ms 31068 KB Output is correct
8 Correct 5 ms 30848 KB Output is correct
9 Correct 5 ms 31064 KB Output is correct
10 Correct 5 ms 31068 KB Output is correct
11 Correct 5 ms 31068 KB Output is correct
12 Correct 5 ms 31068 KB Output is correct
13 Correct 5 ms 31068 KB Output is correct
14 Correct 5 ms 31068 KB Output is correct
15 Correct 5 ms 31068 KB Output is correct
16 Correct 6 ms 31068 KB Output is correct
17 Correct 5 ms 31064 KB Output is correct
18 Correct 5 ms 31064 KB Output is correct
19 Correct 5 ms 31068 KB Output is correct
20 Correct 5 ms 31068 KB Output is correct
21 Correct 6 ms 30920 KB Output is correct
22 Correct 5 ms 31068 KB Output is correct
23 Correct 5 ms 31068 KB Output is correct
24 Correct 6 ms 31064 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31064 KB Output is correct
2 Correct 5 ms 31068 KB Output is correct
3 Correct 4 ms 31068 KB Output is correct
4 Correct 5 ms 30868 KB Output is correct
5 Correct 189 ms 46560 KB Output is correct
6 Correct 181 ms 46708 KB Output is correct
7 Correct 172 ms 46712 KB Output is correct
8 Correct 167 ms 46708 KB Output is correct
9 Correct 5 ms 31064 KB Output is correct
10 Correct 5 ms 31068 KB Output is correct
11 Correct 5 ms 31068 KB Output is correct
12 Correct 6 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 5 ms 31068 KB Output is correct
15 Correct 5 ms 31068 KB Output is correct
16 Correct 5 ms 30848 KB Output is correct
17 Correct 5 ms 31064 KB Output is correct
18 Correct 5 ms 31068 KB Output is correct
19 Correct 5 ms 31068 KB Output is correct
20 Correct 5 ms 31068 KB Output is correct
21 Correct 5 ms 31068 KB Output is correct
22 Correct 5 ms 31068 KB Output is correct
23 Correct 5 ms 31068 KB Output is correct
24 Correct 6 ms 31068 KB Output is correct
25 Correct 5 ms 31064 KB Output is correct
26 Correct 5 ms 31064 KB Output is correct
27 Correct 5 ms 31068 KB Output is correct
28 Correct 5 ms 31068 KB Output is correct
29 Correct 6 ms 30920 KB Output is correct
30 Correct 5 ms 31068 KB Output is correct
31 Correct 5 ms 31068 KB Output is correct
32 Correct 6 ms 31064 KB Output is correct
33 Correct 123 ms 34088 KB Output is correct
34 Correct 92 ms 34140 KB Output is correct
35 Correct 103 ms 34288 KB Output is correct
36 Correct 112 ms 34140 KB Output is correct
37 Correct 25 ms 31908 KB Output is correct
38 Correct 62 ms 34396 KB Output is correct
39 Correct 10 ms 31324 KB Output is correct
40 Correct 59 ms 34124 KB Output is correct
41 Correct 70 ms 34760 KB Output is correct
42 Correct 85 ms 34880 KB Output is correct
43 Correct 83 ms 42456 KB Output is correct
44 Correct 111 ms 40660 KB Output is correct