# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
657585 | 2022-11-10T10:15:49 Z | ktkerem | The Xana coup (BOI21_xanadu) | C++17 | 75 ms | 21288 KB |
/*#pragma GCC target ("avx2") #pragma GCC optimize ("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/ #include<bits/stdc++.h> /**/ //typedef int ll; typedef long long ll; typedef unsigned long long ull; typedef std::string str; /*typedef __int128 vll; typedef unsigned __int128 uvll;*/ #define llll std::pair<ll , ll> #define pb push_back #define pf push_front #define halo cout << "hello\n" #define fi first #define sec second #define all(a) a.begin() , a.end() const ll limit = 998244353; const ll ous = 2e5 + 7; const ll dx[4] = {-1 , 0 , 1 , 0} , dy[4] = {0,1,0,-1}; std::vector<ll> ar;std::vector<ll> adj[ous]; ll n , m; ll dp[ous][2][2]; void dfs(ll crt , ll prv){ ll pt[2][2]; ll ct[2][2]; for(ll i = 0;2>i;i++){ for(ll j = 0;2>j;j++){ dp[crt][i][j] = limit; pt[i][j] = limit; ct[i][j] = limit; } } dp[crt][0][ar[crt]] = 0; dp[crt][1][1 - ar[crt]] = 1; for(auto j:adj[crt]){ if(j != prv){ dfs(j , crt); for(ll i = 0;2>i;i++){ for(ll j = 0;2>j;j++){ pt[i][j] = limit; } } for(ll fp = 0;2>fp;fp++){ for(ll sp = 0;2>sp;sp++){ for(ll tp = 0;2>tp;tp++){ pt[fp][sp ^ tp] = std::min(pt[fp][sp ^ tp] , dp[crt][fp][sp] + dp[j][tp][fp]); } } } for(ll i = 0;2>i;i++){ for(ll j = 0;2>j;j++){ dp[crt][i][j] = pt[i][j]; } } } } } void solve(){ std::cin >> n; for(ll i = 1;n>i;i++){ ll x , y;std::cin >> x >> y; adj[x].pb(y); adj[y].pb(x); } ar.resize(n+1); for(ll i = 1;n>=i;i++){ std::cin >> ar[i]; } dfs(1 , 0); ll ans = std::min(dp[1][0][0] , dp[1][1][0]); if(ans >= limit){ std::cout << "impossible\n"; return; } std::cout << ans << "\n"; } signed main(){ std::ios_base::sync_with_stdio(false);std::cin.tie(NULL); ll t=1; //std::cin >> t >> n >> m; ll o = 1; while(t--){ //cout << "Case " << o++ << ":\n"; solve(); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4948 KB | Output is correct |
2 | Correct | 2 ms | 4948 KB | Output is correct |
3 | Correct | 3 ms | 5032 KB | Output is correct |
4 | Correct | 3 ms | 4944 KB | Output is correct |
5 | Correct | 2 ms | 4948 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4948 KB | Output is correct |
2 | Correct | 2 ms | 4948 KB | Output is correct |
3 | Correct | 3 ms | 5032 KB | Output is correct |
4 | Correct | 3 ms | 4944 KB | Output is correct |
5 | Correct | 2 ms | 4948 KB | Output is correct |
6 | Correct | 3 ms | 4948 KB | Output is correct |
7 | Correct | 2 ms | 4948 KB | Output is correct |
8 | Correct | 3 ms | 4948 KB | Output is correct |
9 | Correct | 3 ms | 4948 KB | Output is correct |
10 | Correct | 4 ms | 5032 KB | Output is correct |
11 | Correct | 3 ms | 4948 KB | Output is correct |
12 | Correct | 4 ms | 4948 KB | Output is correct |
13 | Correct | 4 ms | 5032 KB | Output is correct |
14 | Correct | 3 ms | 4948 KB | Output is correct |
15 | Correct | 3 ms | 4948 KB | Output is correct |
16 | Correct | 3 ms | 4948 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 50 ms | 21084 KB | Output is correct |
2 | Correct | 46 ms | 20940 KB | Output is correct |
3 | Correct | 54 ms | 21196 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 21148 KB | Output is correct |
2 | Correct | 59 ms | 21068 KB | Output is correct |
3 | Correct | 52 ms | 21288 KB | Output is correct |
4 | Correct | 49 ms | 13228 KB | Output is correct |
5 | Correct | 51 ms | 13992 KB | Output is correct |
6 | Correct | 57 ms | 14244 KB | Output is correct |
7 | Correct | 3 ms | 5076 KB | Output is correct |
8 | Correct | 17 ms | 7992 KB | Output is correct |
9 | Correct | 64 ms | 13840 KB | Output is correct |
10 | Correct | 75 ms | 13992 KB | Output is correct |
11 | Correct | 53 ms | 14180 KB | Output is correct |
12 | Correct | 57 ms | 14540 KB | Output is correct |
13 | Correct | 50 ms | 13900 KB | Output is correct |
14 | Correct | 56 ms | 14560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4948 KB | Output is correct |
2 | Correct | 2 ms | 4948 KB | Output is correct |
3 | Correct | 3 ms | 5032 KB | Output is correct |
4 | Correct | 3 ms | 4944 KB | Output is correct |
5 | Correct | 2 ms | 4948 KB | Output is correct |
6 | Correct | 3 ms | 4948 KB | Output is correct |
7 | Correct | 2 ms | 4948 KB | Output is correct |
8 | Correct | 3 ms | 4948 KB | Output is correct |
9 | Correct | 3 ms | 4948 KB | Output is correct |
10 | Correct | 4 ms | 5032 KB | Output is correct |
11 | Correct | 3 ms | 4948 KB | Output is correct |
12 | Correct | 4 ms | 4948 KB | Output is correct |
13 | Correct | 4 ms | 5032 KB | Output is correct |
14 | Correct | 3 ms | 4948 KB | Output is correct |
15 | Correct | 3 ms | 4948 KB | Output is correct |
16 | Correct | 3 ms | 4948 KB | Output is correct |
17 | Correct | 50 ms | 21084 KB | Output is correct |
18 | Correct | 46 ms | 20940 KB | Output is correct |
19 | Correct | 54 ms | 21196 KB | Output is correct |
20 | Correct | 49 ms | 21148 KB | Output is correct |
21 | Correct | 59 ms | 21068 KB | Output is correct |
22 | Correct | 52 ms | 21288 KB | Output is correct |
23 | Correct | 49 ms | 13228 KB | Output is correct |
24 | Correct | 51 ms | 13992 KB | Output is correct |
25 | Correct | 57 ms | 14244 KB | Output is correct |
26 | Correct | 3 ms | 5076 KB | Output is correct |
27 | Correct | 17 ms | 7992 KB | Output is correct |
28 | Correct | 64 ms | 13840 KB | Output is correct |
29 | Correct | 75 ms | 13992 KB | Output is correct |
30 | Correct | 53 ms | 14180 KB | Output is correct |
31 | Correct | 57 ms | 14540 KB | Output is correct |
32 | Correct | 50 ms | 13900 KB | Output is correct |
33 | Correct | 56 ms | 14560 KB | Output is correct |
34 | Correct | 3 ms | 4948 KB | Output is correct |
35 | Correct | 3 ms | 4948 KB | Output is correct |
36 | Correct | 3 ms | 5036 KB | Output is correct |
37 | Correct | 3 ms | 4948 KB | Output is correct |
38 | Correct | 3 ms | 5032 KB | Output is correct |
39 | Correct | 3 ms | 4948 KB | Output is correct |
40 | Correct | 3 ms | 4948 KB | Output is correct |
41 | Correct | 3 ms | 5028 KB | Output is correct |
42 | Correct | 3 ms | 5032 KB | Output is correct |
43 | Correct | 3 ms | 4948 KB | Output is correct |
44 | Correct | 3 ms | 4948 KB | Output is correct |
45 | Correct | 54 ms | 21084 KB | Output is correct |
46 | Correct | 58 ms | 20848 KB | Output is correct |
47 | Correct | 49 ms | 21232 KB | Output is correct |
48 | Correct | 47 ms | 13200 KB | Output is correct |
49 | Correct | 54 ms | 14028 KB | Output is correct |
50 | Correct | 55 ms | 14256 KB | Output is correct |
51 | Correct | 3 ms | 5076 KB | Output is correct |
52 | Correct | 16 ms | 7968 KB | Output is correct |
53 | Correct | 67 ms | 13804 KB | Output is correct |
54 | Correct | 66 ms | 14040 KB | Output is correct |
55 | Correct | 53 ms | 14304 KB | Output is correct |
56 | Correct | 59 ms | 14516 KB | Output is correct |
57 | Correct | 74 ms | 14000 KB | Output is correct |
58 | Correct | 69 ms | 14584 KB | Output is correct |
59 | Correct | 22 ms | 7984 KB | Output is correct |
60 | Correct | 60 ms | 12948 KB | Output is correct |
61 | Correct | 57 ms | 13744 KB | Output is correct |
62 | Correct | 54 ms | 13916 KB | Output is correct |
63 | Correct | 53 ms | 13900 KB | Output is correct |
64 | Correct | 66 ms | 14000 KB | Output is correct |
65 | Correct | 52 ms | 14460 KB | Output is correct |
66 | Correct | 50 ms | 14476 KB | Output is correct |
67 | Correct | 46 ms | 14144 KB | Output is correct |
68 | Correct | 37 ms | 14172 KB | Output is correct |
69 | Correct | 40 ms | 14280 KB | Output is correct |
70 | Correct | 42 ms | 14144 KB | Output is correct |