제출 #448508

#제출 시각아이디문제언어결과실행 시간메모리
448508mariowongThe Xana coup (BOI21_xanadu)C++14
10 / 100
104 ms22468 KiB
#include <bits/stdc++.h> using namespace std; int n,u,v,dfsorder[100005],dp[100005][5][5],ans1,ans2,a[100005]; //first 0 1 closed? //second 0 1 pressed? vector <int> edge[100005],v1,v2; bool vis[100005]; queue <int> q; void dfs(int x){ vis[x]=true; for (int i=0;i<edge[x].size();i++){ if (!vis[edge[x][i]]){ dfsorder[x]++; dfs(edge[x][i]); } } } int main(){ ios::sync_with_stdio(false); cin >> n; for (int i=1;i<n;i++){ cin >> u >> v; edge[u].push_back(v); edge[v].push_back(u); } for (int i=1;i<=n;i++){ cin >> a[i]; } dfs(1); for (int i=1;i<=n;i++){ if (dfsorder[i] == 0) q.push(i); vis[i]=false; dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=1e9; } while (!q.empty()){ u=q.front(); q.pop(); vis[u]=true; ans1=ans2=0; v1.clear(); v2.clear(); for (int i=0;i<edge[u].size();i++){ if (vis[edge[u][i]]){ ans1+=dp[edge[u][i]][0][0]; // off v1.push_back(dp[edge[u][i]][0][1]-dp[edge[u][i]][0][0]); ans2+=dp[edge[u][i]][1][0]; // on v2.push_back(dp[edge[u][i]][1][1]-dp[edge[u][i]][1][0]); } else { dfsorder[edge[u][i]]--; if (dfsorder[edge[u][i]] == 0) q.push(edge[u][i]); } } dp[u][a[u]][0]=min(ans1,dp[u][a[u]][0]); dp[u][1-a[u]][1]=min(ans2+1,dp[u][1-a[u]][1]); sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end()); for (int i=0;i<v1.size();i++){ ans1+=v1[i]; ans2+=v2[i]; if (i%2 == 0){ dp[u][1-a[u]][0]=min(dp[u][1-a[u]][0],ans1); dp[u][a[u]][1]=min(dp[u][a[u]][1],ans2+1); } else { dp[u][a[u]][0]=min(dp[u][a[u]][0],ans1); dp[u][1-a[u]][1]=min(dp[u][1-a[u]][1],ans2+1); } } } if (min(dp[1][0][0],dp[1][0][1]) >= 1e9) cout << "impossible\n"; else cout << min(dp[1][0][0],dp[1][0][1]) << "\n"; return 0; } //1 3 6 10 //2 7 9 //4 5 11 //8

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

xanadu.cpp: In function 'void dfs(int)':
xanadu.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i=0;i<edge[x].size();i++){
      |               ~^~~~~~~~~~~~~~~
xanadu.cpp: In function 'int main()':
xanadu.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (int i=0;i<edge[u].size();i++){
      |                ~^~~~~~~~~~~~~~~
xanadu.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (int i=0;i<v1.size();i++){
      |                ~^~~~~~~~~~
#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...