Submission #889244

#	Time	Username	Problem	Language	Result	Execution time	Memory
889244		Alora	Logičari (COCI21_logicari)	C++17	110 / 110	169 ms	32104 KiB

Main

#include <bits/stdc++.h>
#define Alora "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define int long long
#define ll long long
#define f first
#define se second
#define pii pair<int, int>
#define getbit(i, j) ((i >> j) & 1)
#define all(v) v.begin(), v.end()
#define pb push_back
#define maxn 100005
const int M = 1e9 + 7;
using namespace std;
int n, anc[maxn], cha[maxn], root, special, res = 1e9;
vector <int> g[maxn];

int get(int u){
    if(anc[u] == 0) return u;
    return (anc[u] = get(anc[u]));
}

void dfs(int u, int fa){
    for(auto v: g[u]) if(v != fa){
        cha[v] = u;
        dfs(v, u);
    }
}
int dp[maxn][2][2][2][2];
int cal(int u, int me, int up, int rt, int sp){
    int &ans = dp[u][me][up][rt][sp];
    if(ans != -1) return ans;
    ans = 1e9;

    bool ok = 0;
    if(u == root && me != rt) ok = 1;
    if(u == special && me != sp) ok = 1;
    if(u == special && rt && up) ok = 1;
    if(ok) return (ans = 1e9); // TH vi phạm

    bool covered = 0;
    if(up || (u == root && sp) || (u == special && rt)) covered = 1;

    int sum = me;
    for(auto v: g[u]) if(v != cha[u]){
        sum += cal(v, 0, me, rt, sp);
    }

    if(covered) return (ans = sum); // TH đỉnh u đã đc bao phủ bởi 1 đỉnh màu đen
    for(auto v: g[u]) if(v != cha[u]){
        ans = min(ans, sum - cal(v, 0, me, rt, sp) + cal(v, 1, me, rt, sp));
    }
    return ans;
}
 main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	if(fopen(Alora".inp", "r")){
    freopen(Alora".inp", "r", stdin);
    freopen(Alora".out", "w", stdout);}
    cin >> n;
    fi(i, 1, n){
        int u, v; cin >> u >> v;
        int p = get(u), q = get(v);
        if(p != q){
            anc[p] = q;
            g[u].pb(v); g[v].pb(u);
        }
        else root = u, special = v;
        // xóa 1 cạnh trong chu trình để tạo thành cây -> dp trêm cây.
        // đánh dâu lại 2 đỉnh này, 1 đỉnh làm gốc, 1 đỉnh là special
    }

    memset(dp, -1, sizeof(dp));
    dfs(root, 0);
    fi(rt, 0, 1)
        fi(sp, 0, 1)
            res = min(res, cal(root, rt, 0, rt, sp));

    if(res == 1e9) cout << -1;
    else cout << res;

    return 0;
}

Compilation message (stderr)

Main.cpp:56:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 |  main(){
      |  ^~~~
Main.cpp: In function 'int main()':
Main.cpp:60:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     freopen(Alora".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:61:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     freopen(Alora".out", "w", stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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