oj.uz

Submission #889239

# Submission time Handle Problem Language Result Execution time Memory
889239 2023-12-19T08:32:45 Z Alora Logičari (COCI21_logicari) C++17
10 / 110
 172 ms 27048 KB 
#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 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;
}
int 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

Main.cpp: In function 'int main()':
Main.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     freopen(Alora".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen(Alora".out", "w", stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 117 ms 27040 KB Output is correct
6 Correct 110 ms 27048 KB Output is correct
7 Correct 172 ms 26960 KB Output is correct
8 Correct 147 ms 26880 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 9048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 9048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 117 ms 27040 KB Output is correct
6 Correct 110 ms 27048 KB Output is correct
7 Correct 172 ms 26960 KB Output is correct
8 Correct 147 ms 26880 KB Output is correct
9 Incorrect 1 ms 9048 KB Output isn't correct
10 Halted 0 ms 0 KB -