Submission #1260973

#TimeUsernameProblemLanguageResultExecution timeMemory
1260973icebearCats or Dogs (JOI18_catdog)C++20
38 / 100
3094 ms6988 KiB
// ~~ icebear ~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; template<class T> bool minimize(T &a, const T &b) { if (a > b) return a = b, true; return false; } template<class T> bool maximize(T &a, const T &b) { if (a < b) return a = b, true; return false; } #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORR(i,a,b) for(int i=(a); i>=(b); --i) #define REP(i, n) for(int i=0; i<(n); ++i) #define RED(i, n) for(int i=(n)-1; i>=0; --i) #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define task "icebear" const int MOD = 1e9 + 7; const int inf = 1e9 + 27092008; const ll INF = 1e18 + 27092008; const int N = 1e5 + 5; int n, q; vector<int> G[N]; int f[N][3], state[N]; void initialize(int N, vector<int> A, vector<int> B) { n = N; FOR(i, 0, N - 2) { G[A[i]].pb(B[i]); G[B[i]].pb(A[i]); } } void dfs(int u, int par) { if (state[u] == 0) f[u][0] = f[u][1] = f[u][2] = 0; else f[u][state[u]] = 0; for(int v : G[u]) if (v != par) { dfs(v, u); f[u][0] = min(inf, f[u][0] + min({f[v][0], f[v][1] + 1, f[v][2] + 1})); f[u][1] = min(inf, f[u][1] + min({f[v][1], f[v][0], f[v][2] + 1})); f[u][2] = min(inf, f[u][2] + min({f[v][2], f[v][0], f[v][1] + 1})); } } int cat(int v) { state[v] = 1; memset(f, 0x3f, sizeof f); dfs(1, -1); return min({f[1][0], f[1][1], f[1][2]}); } int dog(int v) { state[v] = 2; memset(f, 0x3f, sizeof f); dfs(1, -1); return min({f[1][0], f[1][1], f[1][2]}); } int neighbor(int v) { state[v] = 0; memset(f, 0x3f, sizeof f); dfs(1, -1); return min({f[1][0], f[1][1], f[1][2]}); } //void init(void) { // initialize(n, A, B); //} // //void process(void) { // cin >> q; // while(q--) { // int t, v; // cin >> t >> v; // if (t == 1) cat(v); // else if (t == 2) dog(v); // else neighbor(v); // memset(f, 0x3f, sizeof f); // dfs(1, -1); // cout << min({f[1][0], f[1][1], f[1][2]}) << '\n'; // } //} // //int main() { // ios_base::sync_with_stdio(0); // cin.tie(0); cout.tie(0); // if (fopen(task".inp", "r")) { // freopen(task".inp", "r", stdin); // freopen(task".out", "w", stdout); // } // int tc = 1; //// cin >> tc; // while(tc--) { // init(); // process(); // } // return 0; //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...