Submission #487129

#	Time	Username	Problem	Language	Result	Execution time	Memory
487129		JovanB	Logičari (COCI21_logicari)	C++17	110 / 110	71 ms	21440 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 100000;
const ll INF = 1000000;

vector <int> graf[N+5];
vector <int> cyc;
bool in_cycle[N+5];
ll dp[N+5][2][2];
ll pd[2][2][2][2];
ll ppd[2][2][2][2];
bool visited[N+5];

int pcc;

bool dfs_cycle(int v, int p){
    visited[v] = 1;
    for(auto c : graf[v]){
        if(c == p) continue;
        if(visited[c]){
            pcc = c;
            cyc.push_back(v);
            return 1;
        }
        if(dfs_cycle(c, v)){
            if(pcc) cyc.push_back(v);
            if(v == pcc) pcc = 0;
            return 1;
        }
    }
    return 0;
}

void dfs(int v, int p){
    dp[v][0][0] = dp[v][0][1] = dp[v][1][0] = dp[v][1][1] = INF;
    vector <int> vec;
    for(auto c : graf[v]){
        if(in_cycle[c] || c == p) continue;
        dfs(c, v);
        vec.push_back(c);
    }
    /// ukljucen, sat
    if(!vec.empty()){
        dp[v][1][1] = 1;
        ll mn = dp[vec[0]][1][0] - dp[vec[0]][0][0];
        for(auto c : vec){
            dp[v][1][1] += dp[c][0][0];
            mn = min(mn, dp[c][1][0] - dp[c][0][0]);
        }
        dp[v][1][1] += mn;
    }
    /// ukljucen, nesat
    dp[v][1][0] = 1;
    for(auto c : vec) dp[v][1][0] += dp[c][0][0];
    /// neukljucen, sat
    if(!vec.empty()){
        dp[v][0][1] = 0;
        ll mn = dp[vec[0]][1][1] - dp[vec[0]][0][1];
        for(auto c : vec){
            dp[v][0][1] += dp[c][0][1];
            mn = min(mn, dp[c][1][1] - dp[c][0][1]);
        }
        dp[v][0][1] += mn;
    }
    /// neukljucen, nesat
    dp[v][0][0] = 0;
    for(auto c : vec) dp[v][0][0] += dp[c][0][1];
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    if(!dfs_cycle(1, 0)){
        return 0;
        dfs(1, 0);
        ll res = INF;
        for(int j=0; j<=1; j++) for(int k=0; k<=1; k++) res = min(res, dp[1][j][k]);
        cout << (res >= INF ? -1 : res) << "\n";
        return 0;
    }
    for(auto v : cyc) in_cycle[v] = 1;
    for(auto v : cyc) dfs(v, 0);
    int x = cyc.back();
    cyc.pop_back();
    int y = cyc.back();
    cyc.pop_back();
    for(int a=0; a<=1; a++) for(int b=0; b<=1; b++) for(int c=0; c<=1; c++) for(int d=0; d<=1; d++) pd[a][b][c][d] = INF;
    for(int a=0; a<=1; a++) for(int b=0; b<=1; b++) for(int c=0; c<=1; c++) for(int d=0; d<=1; d++){
        if(a && d){
            continue;
        }
        if(c && b){
            continue;
        }
        pd[a][b | c][c][d | a] = min(pd[a][b |c][c][d | a], dp[x][a][b] + dp[y][c][d]);
    }
    reverse(cyc.begin(), cyc.end());
    for(auto v : cyc){
        for(int a=0; a<=1; a++) for(int b=0; b<=1; b++) for(int c=0; c<=1; c++) for(int d=0; d<=1; d++) ppd[a][b][c][d] = pd[a][b][c][d], pd[a][b][c][d] = INF;
        for(int a=0; a<=1; a++) for(int b=0; b<=1; b++) for(int c=0; c<=1; c++) for(int d=0; d<=1; d++){
            for(int e=0; e<=1; e++){
                for(int f=0; f<=1; f++){
                    if(a && d) continue;
                    if(b && c) continue;
                    if(!b && !c) continue;
                    pd[e][f][c][d | a] = min(pd[e][f][c][d | a], ppd[e][f][a][b] + dp[v][c][d]);
                }
            }
        }
    }
    ll res = INF;
    for(int a=0; a<=1; a++) for(int b=0; b<=1; b++) for(int c=0; c<=1; c++) for(int d=0; d<=1; d++){
        if(a && d) continue;
        if(b && c) continue;
        if(!a && !d) continue;
        if(!b && !c) continue;
        res = min(res, pd[a][b][c][d]);
    }
    cout << (res >= INF ? -1 : res) << "\n";
    return 0;
}

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