oj.uz

Submission #741261

# Submission time Handle Problem Language Result Execution time Memory
741261 2023-05-14T00:21:39 Z Pichon5 Logičari (COCI21_logicari) C++17
110 / 110
 253 ms 33180 KB 
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <sstream>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define jumanji ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define F first
#define S second
#define int long long
#define vi vector<int>
#define ll long long
using namespace std;
 
vector<vi>G;
vi vis;
//fin endpoints of one edge in a cycle of an undirected graph
int A,B;
const int tam=1e5+100;
const int INF=1e9;
int dp[tam][2][2][2][2];
void dfs(int u,int p){
    vis[u]=1;
    for(auto v:G[u]){
        if(v==p)continue;
        if(vis[v]==1){
            A=u;
            B=v;
            return;
        }
        if(vis[v]==0){
            dfs(v,u);
            if(A!=-1)return;
        }
    }
    vis[u]=2;
}
int f(int nodo, int c,int cP, int cA, int cB, int padre){
    if(dp[nodo][c][cP][cA][cB] != -1) return dp[nodo][c][cP][cA][cB];
    if(nodo==A && c!=cA)return dp[nodo][c][cP][cA][cB]=INF;
    if(nodo==B && c!=cB)return dp[nodo][c][cP][cA][cB]=INF;
    if(nodo==B && cA && cP)return dp[nodo][c][cP][cA][cB]=INF;
    bool ok=0;
    if(cP)ok=1;
    if(nodo==A && cB)ok=1;
    if(nodo==B && cA)ok=1;
    int sum=c;
    for(auto v:G[nodo]){
        if(v==padre)continue;
        sum+=f(v,0,c,cA,cB,nodo);
    }
    dp[nodo][c][cP][cA][cB]=INF;
    if(ok){
        dp[nodo][c][cP][cA][cB]=sum;
    }else{
        for(auto v:G[nodo]){
            if(v==padre)continue;
            dp[nodo][c][cP][cA][cB]=min(dp[nodo][c][cP][cA][cB],sum-f(v,0,c,cA,cB,nodo)+f(v,1,c,cA,cB,nodo));
        }
    }
    return dp[nodo][c][cP][cA][cB];
}
signed main(){
    memset(dp,-1,sizeof dp);
    int n,a,b;
    cin>>n;
    vector<pair<int,int>>edges;
    G.resize(n+1);
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        G[a].pb(b);
        G[b].pb(a);
        edges.pb({a,b});
    }
    vis.assign(n+1,0);
    A=-1;
    B=-1;
    dfs(1,-1);
    G.clear();
    G.resize(n+1);
    for(auto e:edges){
        if(e.F==A && e.S==B)continue;
        if(e.F==B && e.S==A)continue;
        G[e.F].pb(e.S);
        G[e.S].pb(e.F);
    }
    ll res=INF;
    res=min(res,f(A,0,0,0,0,-1));
    res=min(res,f(A,0,0,0,1,-1));
    res=min(res,f(A,1,0,1,0,-1));
    res=min(res,f(A,1,0,1,1,-1));
    if(res>=INF)cout<<-1<<endl;
    else cout<<res<<endl;
 
 
 
 
    return 0;
}  
//Guess i wont be comming to church on sunday

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 5 ms 12820 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 5 ms 12756 KB Output is correct
5 Correct 236 ms 33164 KB Output is correct
6 Correct 232 ms 33076 KB Output is correct
7 Correct 253 ms 33088 KB Output is correct
8 Correct 228 ms 33180 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 5 ms 12756 KB Output is correct
5 Correct 6 ms 12728 KB Output is correct
6 Correct 5 ms 12756 KB Output is correct
7 Correct 5 ms 12756 KB Output is correct
8 Correct 7 ms 12756 KB Output is correct
9 Correct 5 ms 12756 KB Output is correct
10 Correct 5 ms 12800 KB Output is correct
11 Correct 5 ms 12756 KB Output is correct
12 Correct 6 ms 12756 KB Output is correct
13 Correct 6 ms 12884 KB Output is correct
14 Correct 7 ms 12884 KB Output is correct
15 Correct 6 ms 12884 KB Output is correct
16 Correct 7 ms 12884 KB Output is correct
17 Correct 5 ms 12756 KB Output is correct
18 Correct 6 ms 12804 KB Output is correct
19 Correct 6 ms 12756 KB Output is correct
20 Correct 6 ms 12884 KB Output is correct
21 Correct 7 ms 12832 KB Output is correct
22 Correct 6 ms 12884 KB Output is correct
23 Correct 6 ms 13012 KB Output is correct
24 Correct 6 ms 12884 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 5 ms 12820 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 5 ms 12756 KB Output is correct
5 Correct 236 ms 33164 KB Output is correct
6 Correct 232 ms 33076 KB Output is correct
7 Correct 253 ms 33088 KB Output is correct
8 Correct 228 ms 33180 KB Output is correct
9 Correct 5 ms 12756 KB Output is correct
10 Correct 5 ms 12756 KB Output is correct
11 Correct 7 ms 12756 KB Output is correct
12 Correct 5 ms 12756 KB Output is correct
13 Correct 6 ms 12728 KB Output is correct
14 Correct 5 ms 12756 KB Output is correct
15 Correct 5 ms 12756 KB Output is correct
16 Correct 7 ms 12756 KB Output is correct
17 Correct 5 ms 12756 KB Output is correct
18 Correct 5 ms 12800 KB Output is correct
19 Correct 5 ms 12756 KB Output is correct
20 Correct 6 ms 12756 KB Output is correct
21 Correct 6 ms 12884 KB Output is correct
22 Correct 7 ms 12884 KB Output is correct
23 Correct 6 ms 12884 KB Output is correct
24 Correct 7 ms 12884 KB Output is correct
25 Correct 5 ms 12756 KB Output is correct
26 Correct 6 ms 12804 KB Output is correct
27 Correct 6 ms 12756 KB Output is correct
28 Correct 6 ms 12884 KB Output is correct
29 Correct 7 ms 12832 KB Output is correct
30 Correct 6 ms 12884 KB Output is correct
31 Correct 6 ms 13012 KB Output is correct
32 Correct 6 ms 12884 KB Output is correct
33 Correct 169 ms 20296 KB Output is correct
34 Correct 165 ms 20296 KB Output is correct
35 Correct 163 ms 20304 KB Output is correct
36 Correct 203 ms 20292 KB Output is correct
37 Correct 37 ms 14668 KB Output is correct
38 Correct 154 ms 20348 KB Output is correct
39 Correct 14 ms 13492 KB Output is correct
40 Correct 152 ms 20216 KB Output is correct
41 Correct 112 ms 22140 KB Output is correct
42 Correct 116 ms 21924 KB Output is correct
43 Correct 190 ms 33068 KB Output is correct
44 Correct 175 ms 27620 KB Output is correct