# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
414702 | 2021-05-31T04:39:01 Z | juggernaut | The Xana coup (BOI21_xanadu) | C++17 | 267 ms | 114632 KB |
#include<bits/stdc++.h> #define fr first #define sc second using namespace std; void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} typedef long long ll; #define USING_ORDERED_SET 0 #if USING_ORDERED_SET #include<bits/extc++.h> using namespace __gnu_pbds; template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; #endif template<class T>void umax(T &a,T b){if(a<b)a=b;} template<class T>void umin(T &a,T b){if(b<a)a=b;} #ifdef IOI2021SG #define printl(args...)printf(args) #else #define printl(args...)((void)0) #endif int mp[2000000]; vector<int>g[100005]; int n; int run(int mask){ if(~mp[mask])return mp[mask]; mp[mask]=2e9; for(int i=0;i<n;i++){ int new_mask=mask; for(int to:g[i])new_mask^=(1<<to); umin(mp[mask],run(new_mask)+1); } return mp[mask]; } int main(){ memset(mp,-1,sizeof mp); scanf("%d",&n); for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); x--;y--; g[x].push_back(y); g[y].push_back(x); } int mask=0; for(int i=0;i<n;i++){ int x; scanf("%d",&x); mask|=(x<<i); g[i].push_back(i); } mp[mask]=0; int x=run(0); if(x==int(2e9))puts("impossible"); else printf("%d",x); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 13516 KB | Output is correct |
2 | Correct | 8 ms | 11200 KB | Output is correct |
3 | Correct | 132 ms | 35160 KB | Output is correct |
4 | Correct | 267 ms | 59692 KB | Output is correct |
5 | Correct | 115 ms | 34968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 13516 KB | Output is correct |
2 | Correct | 8 ms | 11200 KB | Output is correct |
3 | Correct | 132 ms | 35160 KB | Output is correct |
4 | Correct | 267 ms | 59692 KB | Output is correct |
5 | Correct | 115 ms | 34968 KB | Output is correct |
6 | Correct | 15 ms | 13540 KB | Output is correct |
7 | Correct | 8 ms | 11212 KB | Output is correct |
8 | Correct | 125 ms | 34976 KB | Output is correct |
9 | Correct | 262 ms | 59656 KB | Output is correct |
10 | Correct | 117 ms | 35032 KB | Output is correct |
11 | Runtime error | 17 ms | 20932 KB | Execution killed with signal 11 |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 145 ms | 114632 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 144 ms | 114616 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 13516 KB | Output is correct |
2 | Correct | 8 ms | 11200 KB | Output is correct |
3 | Correct | 132 ms | 35160 KB | Output is correct |
4 | Correct | 267 ms | 59692 KB | Output is correct |
5 | Correct | 115 ms | 34968 KB | Output is correct |
6 | Correct | 15 ms | 13540 KB | Output is correct |
7 | Correct | 8 ms | 11212 KB | Output is correct |
8 | Correct | 125 ms | 34976 KB | Output is correct |
9 | Correct | 262 ms | 59656 KB | Output is correct |
10 | Correct | 117 ms | 35032 KB | Output is correct |
11 | Runtime error | 17 ms | 20932 KB | Execution killed with signal 11 |
12 | Halted | 0 ms | 0 KB | - |