제출 #823884

#제출 시각아이디문제언어결과실행 시간메모리
823884tsetThe Xana coup (BOI21_xanadu)C++14
10 / 100
57 ms27456 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18 + 42; vector<vector<int> > nxt; vector<vector<int>> filsDe; vector<int> pereDe; vector<vector<vector<int > > > dp; vector<int > initState; void dfsInit(int nde,int prc ) { pereDe[nde] = prc; for(int iV: nxt[nde]) { if(iV != prc) { filsDe[nde].push_back(iV); dfsInit(iV, nde); } } } int fDP(int isParentT, int isMeT, int nde) { if(dp[isParentT][isMeT][nde] != INF) { return dp[isParentT][isMeT][nde]; } int nbFils = filsDe[nde].size(); int totT = isParentT + isMeT + initState[nde]; int ans = INF; if(totT %2 == 0) //////////////////////////////////////// {//We need to toggle 0 or two child(ren). if(nbFils == 0) { ans = 0; } if(nbFils == 1) { ans = fDP(isMeT, 0, filsDe[nde][0]); } if(nbFils == 2) { ans = min(fDP(isMeT, 0, filsDe[nde][0]) + fDP(isMeT, 0, filsDe[nde][1]), fDP(isMeT, 1, filsDe[nde][0]) + fDP(isMeT, 1, filsDe[nde][1]) + 2); } } else { //We need to toggle only one child. if(nbFils == 0) { ans = INF; } if(nbFils == 1) { ans = fDP(isMeT, 1, filsDe[nde][0]) + 1; } if(nbFils == 2) { ans = min(fDP(isMeT, 0, filsDe[nde][0]) + fDP(isMeT, 1, filsDe[nde][1]) + 1, fDP(isMeT, 1, filsDe[nde][0]) + fDP(isMeT, 0, filsDe[nde][1]) + 1); } } dp[isParentT][isMeT][nde] = ans; return dp[isParentT][isMeT][nde]; } signed main() { int N; scanf("%lld", &N); int nbArretes = N-1; nxt.resize(N+1); filsDe.resize(N+1); pereDe.resize(N+1); for(int iA = 0; iA < nbArretes; iA++) { int u, v; scanf("%lld%lld", &u, &v); nxt[u].push_back(v); nxt[v].push_back(u); } dfsInit(1, 1); initState.resize(N+1); for(int iNde = 1; iNde <=N; iNde++) { scanf("%lld", &initState[iNde]); } dp.resize(2, vector<vector<int>>(2, vector<int>(N+1, INF))); int ans = fDP(0, 0, 1); ans = min(ans, fDP(0, 1, 1) + 1); if(ans > INF) printf("impossible\n"); else printf("%lld", ans); }

컴파일 시 표준 에러 (stderr) 메시지

xanadu.cpp: In function 'int main()':
xanadu.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%lld", &N);
      |     ~~~~~^~~~~~~~~~~~
xanadu.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%lld%lld", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
xanadu.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%lld", &initState[iNde]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...