제출 #863455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
863455		3omar_ahmed	Logičari (COCI21_logicari)	C++17	10 / 110	141 ms	34480 KiB

Main

#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 ans = 1e9;

    memset(dp, -1, sizeof(dp));
    
    if(extra.first == 1) {
        int a = solve(1, 1, 0, 0, 0, 0);
        int b = solve(1, 1, 0, 1, 1, 0) + 1;
        int c = solve(1, 1, 0, 0, 0, 1) + 1;
        int d = solve(1, 1, 0, 1, 1, 1) + 2;

        ans = min({a, b, c, d});
    } else if(extra.second == 1) {
        int a = solve(1, 1, 0, 0, 0, 0);
        int b = solve(1, 1, 0, 0, 1, 0) + 1;
        int c = solve(1, 1, 0, 1, 0, 1) + 1;
        int d = solve(1, 1, 0, 1, 1, 1) + 2;

        ans = min({a, b, c, d});
    } else {
        int a = solve(1, 1, 0, 0, 0, 0);
        int b = solve(1, 1, 0, 0, 1, 0) + 1;
        int c = solve(1, 1, 0, 0, 0, 1) + 1;
        int d = solve(1, 1, 0, 0, 1, 1) + 2;

        int e = solve(1, 1, 0, 1, 0, 0) + 1;
        int f = solve(1, 1, 0, 1, 1, 0) + 2;
        int g = solve(1, 1, 0, 1, 0, 1) + 2;
        int h = solve(1, 1, 0, 1, 1, 1) + 3;
        
        ans = min({a, b, c, d, e, f, g, h});
    }

    if(ans > 1e8) ans = -1;
    cout << ans << endl;
    return 0 ;
}

컴파일 시 표준 에러 (stderr) 메시지

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: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40
• Subtask 4: 0 / 50