| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1118824 | Requiem | Cats or Dogs (JOI18_catdog) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#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, 0, n - 1){
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;
}
}
void initialize(int N, vector<int> A, vector<int> B){
n = N;
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 subtask1::solve();
}
int dog(int u){
dogNode[u] = true;
return subtask1::solve();
}
int neighbor(int u){
catNode[u] = dogNode[u] = false;
return subtask1::solve();
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
int n, q;
vector<int> a, b;
cin >> n >> q;
FOR(i, 1, n - 1){
int u, v;
cin >> u >> v;
a.pb(u);
b.pb(v);
}
initialize(n, a, b);
FOR(i, 1, q){
int u;
string type;
cin >> type >> u;
if (type == "dog") {
cout << dog(u) << endl;
}
else if (type == "cat"){
cout << cat(u) << endl;
}
else{
cout << neighbor(u) << endl;
}
}
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/