제출 #444246

#제출 시각아이디문제언어결과실행 시간메모리
444246parsabahramiThe Xana coup (BOI21_xanadu)C++17
30 / 100
100 ms35144 KiB
/* I do it for the glory */ #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; #define SZ(x) (int) x.size() #define F first #define S second const int N = 1e6 + 10, MOD = 1e9 + 7; int n, C[N], dp[2][2][N]; vector<int> adj[N]; // [root ro zadim ya na][root akharesh chie][root] :clown: void DFS(int v, int p = -1) { if (SZ(adj[v]) < 2 && v > 1) { dp[0][C[v]][v] = 0; dp[0][C[v] ^ 1][v] = dp[1][C[v]][v] = MOD; dp[1][!C[v]][v] = 1; return; } for (int &u : adj[v]) if (u != p) DFS(u, v); int c = 0, m = MOD; for (int &u : adj[v]) { if (u != p) { if (dp[1][0][u] <= dp[0][0][u]) c++; m = min(m, abs(dp[1][0][u] - dp[0][0][u])); } } for (int &u : adj[v]) { if (u != p) { dp[0][(c & 1) ^ C[v]][v] += min(dp[1][0][u], dp[0][0][u]); } } dp[0][(c & 1) ^ C[v] ^ 1][v] = dp[0][(c & 1) ^ C[v]][v] + m; c = 0, m = MOD; for (int &u : adj[v]) { if (u != p) { if (dp[1][1][u] <= dp[0][1][u]) c++; m = min(m, abs(dp[1][1][u] - dp[0][1][u])); } } for (int &u : adj[v]) { if (u != p) { dp[1][(c & 1) ^ C[v] ^ 1][v] += min(dp[1][1][u], dp[0][1][u]); } } dp[1][(c & 1) ^ C[v] ^ 1][v]++; dp[1][(c & 1) ^ C[v]][v] = dp[1][(c & 1) ^ C[v] ^ 1][v] + m; } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } for (int i = 1; i <= n; i++) scanf("%d", &C[i]); DFS(1); printf(min(dp[1][0][1], dp[0][0][1]) > n ? "impossible\n" : "%d\n", min(dp[1][0][1], dp[0][0][1])); return 0; }

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

xanadu.cpp: In function 'int main()':
xanadu.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
xanadu.cpp:59:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~
xanadu.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d", &C[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...