Submission #733626

#TimeUsernameProblemLanguageResultExecution timeMemory
733626n0sk1llCats or Dogs (JOI18_catdog)C++17
0 / 100
2 ms2644 KiB
#include <bits/stdc++.h> #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0) #define mp make_pair #define xx first #define yy second #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define all(x) x.begin(),x.end() #define ff(i,a,b) for (int i = a; i < b; i++) #define fff(i,a,b) for (int i = a; i <= b; i++) #define bff(i,a,b) for (int i = b-1; i >= a; i--) #define bfff(i,a,b) for (int i = b; i >= a; i--) using namespace std; long double typedef ld; unsigned int typedef ui; long long int typedef li; pair<int,int> typedef pii; pair<li,li> typedef pli; pair<ld,ld> typedef pld; vector<vector<int>> typedef graph; unsigned long long int typedef ull; //const int mod = 998244353; const int mod = 1000000007; //Note to self: Check for overflow #include "catdog.h" int n; int kolko=0; //kolko ukupno ukljucenih; ako nije niko ukljucen treba vratiti 0... graph g(100005); li dp[100005][3]; //closed, open cat, open dog int ko[100005]; //0 = niko, 1 = cat, 2 = dog void dfs(int p, int q) { dp[p][1]=0,dp[p][2]=0; for (auto it : g[p]) if (it!=q) { dfs(it,p); dp[p][1]+=min(dp[it][0],dp[it][1]); dp[p][2]+=min(dp[it][0],dp[it][2]); } if (ko[p]==1) dp[p][2]=mod; if (ko[p]==2) dp[p][1]=mod; dp[p][0]=min(dp[p][1],dp[p][2])+1; } int solve() { if (kolko==0) return 0; return dfs(1,0),dp[1][0]; } void initialize(int N, vector<int> A, vector<int> B) { n=N; ff(i,0,n-1) g[A[i]].pb(B[i]),g[B[i]].pb(A[i]); } int cat(int v) { kolko++,ko[v]=1; return solve(); } int dog(int v) { kolko++,ko[v]=2; return solve(); } int neighbor(int v) { kolko--,ko[v]=0; return solve(); } /* 6 1 2 1 3 1 4 4 5 4 6 4 1 5 2 6 2 3 1 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...