제출 #1118843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118843		Requiem	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3048 ms	12616 KiB

catdog

#include "catdog.h"
#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e9
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "catdogs"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Cat / Dogs:

Cho 1 cây n đỉnh với n - 1 cạnh.

Một số đỉnh có màu đỏ / xanh.

Tìm tập cạnh tối thiểu sao cho:
==> trên đường đi giữa 1 cặp đỉnh xanh / đỏ bất kì đều tồn tại 1 cạnh trong tập đã chọn

subtask 2: N <= 1000, Q <= 1000.
O(N * Q).
Ta dựng cây lên.
Với 1 subtree của thằng u, ta nhận coi là nó là thằng blue / red.

Nếu số thằng blue > red thì mình cho blue lên, và chặn hết đống red.
**/
const int MAXN = 3e5 + 9;
int n;
ii edge[MAXN];
vector<int> g[MAXN];
bool catNode[MAXN], dogNode[MAXN];

namespace subtask1{
    bool check(){
        return n <= 20;
    }

    int del[MAXN], ans = inf;


    bool dfs(int u, int p, int d){

        if (catNode[u] and d == 0) return false;

        for(auto id: g[u]){
            int v = edge[id].se + edge[id].fi - u;
            if (v == p) continue;

            int newD = d | del[id];
            if (!dfs(v, u, newD)) return false;
        }
        return true;
    }

    bool valid(){
        FOR(i, 1, n){
            if (dogNode[i] and !dfs(i, -1, 0)) return false;
        }
        return true;
    }

    void backtrack(int pos, int numDel){
        if (pos == n){
            if (valid()) minimize(ans, numDel);
            return;
        }

        backtrack(pos + 1, numDel);
        del[pos] = 1;
        backtrack(pos + 1, numDel + 1);
        del[pos] = 0;
    }
    int solve(){
        ans = inf;
        backtrack(0, 0);
        return ans;
    }
}

namespace subtask2{
    bool check(){
        return n <= 1000;
    }

    int dp[MAXN], ans = 0;


    void dfs(int u, int p){

        int numDog = 0;
        int numCat = 0;

        for(auto id: g[u]){
            int v = edge[id].fi + edge[id].se - u;
            if (v == p) continue;

            dfs(v, u);

            if (dp[v] > 0) numDog++;
            else if (dp[v] < 0) numCat++;
        }

        if (dogNode[u]) {
            ans += numCat;
            dp[u] = 1;
        }
        else if (catNode[u]){
            ans += numDog;
            dp[u] = -1;
        }
        else {
            ans += min(numCat, numDog);
            if (numCat < numDog) dp[u] = 1;
            else if (numCat > numDog) dp[u] = -1;
        }

//        cout << u << ' ' << numCat << ' ' << numDog << endl;
    }

    int solve(){
        ans = 0;
        FOR(i, 1, n){
            dp[i] = 0;
        }
        dfs(1, -1);
        return ans;
    }
}
void initialize(int N, vector<int> A, vector<int> B){
    n = N;
    memset(catNode, false, sizeof(catNode));
    memset(dogNode, false, sizeof(dogNode));
    FOR(i, 0, n - 2){
        edge[i] = {A[i], B[i]};
        g[A[i]].pb(i);
        g[B[i]].pb(i);
    }
}

int cat(int u){
    catNode[u] = true;
    return subtask2::solve();

}

int dog(int u){
    dogNode[u] = true;
    return subtask2::solve();
}

int neighbor(int u){
    catNode[u] = dogNode[u] = false;
    return subtask2::solve();
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 0 / 62