oj.uz

답안 #863462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
863462 2023-10-20T11:44:20 Z 3omar_ahmed Logičari (COCI21_logicari) C++17
0 / 110
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
const int N = 1e5 + 5;

int n;
vector < int > tim;
int dp[N][2][2][2][2];
vector < vector < int >> adj;
pair < int , int > extra = {-1, -1};

void dfs(int node, int par) {
    for(auto ch : adj[node]) {
        if(ch == par) continue;
        if(tim[ch] < tim[node]) {
            extra = {node, ch};
        } else {
            tim[ch] = tim[node] + 1;
            dfs(ch, node);
        }
    }
}


int solve(int node, int par, int color_par, int color_node, int color_extra1, int color_extra2) {
    auto &ret = dp[node][color_par][color_node][color_extra1][color_extra2];
    if(ret != -1) {
        return ret;
    }

    int counter = color_par;
    for(auto child : adj[node]) {
        if(child == par) continue;
        if(child == extra.first) {
            counter += color_extra1;
        } else if(child == extra.second) {
            counter += color_extra2;
        }
    }

    if(node == extra.first) counter += color_extra2;
    else if(node == extra.second) counter += color_extra1;

    if(counter >= 2) {
        return ret = 1e9;
    } else if(counter == 1) {
        int ans = 0;
        for(auto child : adj[node]) {
            if(child == par) continue;
            if(child == extra.first) {
                ans += solve(child, node, color_node, color_extra1, color_extra1, color_extra2);
            } else if(child == extra.second) {
                ans += solve(child, node, color_node, color_extra2, color_extra1, color_extra2);
            } else {
                ans += solve(child, node, color_node, 0, color_extra1, color_extra2); 
            }
        }
        return ret = ans;
    } else {
        int ans = 0, mx = -1e16;
        for(auto child : adj[node]) {
            if(child == par) continue;
            if(child == extra.first) {
                ans += solve(child, node, color_node, color_extra1, color_extra1, color_extra2);
            } else if(child == extra.second) {
                ans += solve(child, node, color_node, color_extra2, color_extra1, color_extra2);
            } else {
                int b = solve(child, node, color_node, 1, color_extra1, color_extra2) + 1; 
                int a = solve(child, node, color_node, 0, color_extra1, color_extra2);
                ans += a, mx = max(mx, a - b);
            }
        }
        if(mx < -1e15) return 1e9;
        return ret = ans - mx;
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    cin >> n;
    tim = vector < int > (n + 1);
    adj = vector < vector < int >> (n + 1);
    for(int i = 0 ; i < n ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }    

    dfs(1, 1);
    
    for(int i = 0 ; i < adj[extra.first].size() ; i++) {
        if(adj[extra.first][i] == extra.second) {
            adj[extra.first].erase(adj[extra.first].begin() + i);
            break;
        }
    }

    for(int i = 0 ; i < adj[extra.second].size() ; i++) {
        if(adj[extra.second][i] == extra.first) {
            adj[extra.second].erase(adj[extra.second].begin() + i);
            break;
        }
    }

    cerr << extra.first << " " << extra.second << endl;

    int a = solve(extra.first, extra.first, 0, 0, 0, 0);
    int b = solve(extra.first, extra.first, 0, 1, 1, 0) + 1;
    int c = solve(extra.first, extra.first, 0, 0, 0, 1) + 1;
    int d = solve(extra.first, extra.first, 0, 1, 1, 1) + 2;

    cerr << a << " " << b << " " << c << " " << d << endl;
    
    int ans = min({a, b, c, d});
    if(ans > 1e8) ans = -1;
    cout << ans << endl;
    return 0 ;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:96:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 0 ; i < adj[extra.first].size() ; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:103:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i = 0 ; i < adj[extra.second].size() ; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -