# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
871791 | 2023-11-11T15:27:12 Z | 1075508020060209tc | Tug of War (BOI15_tug) | C++14 | 283 ms | 28704 KB |
#pragma GCC optimize ("O3") #include<bits/stdc++.h> //#include <bits/extc++.h> //using namespace __gnu_pbds; using namespace std; #define int long long #define X first #define Y second int lowbit(int x){return x&-x;} int n;int K; vector<int>e[500005]; int vis[500005]; int vise[500005]; int dgr[500005]; int ar[500005];int br[500005];int cr[500005]; int basea; int baseb; bitset<600005>dp; bitset<600005>dp2; bitset<600005>zer; int tota;int totb; int tp; void dfs(int nw){ vis[nw]=1; //cout<<nw<<"kk"<<endl; for(int i=0;i<e[nw].size();i++){ int id=e[nw][i]; if(vise[id]){continue;} if(tp==0){ tota+=cr[id]; }else{ totb+=cr[id]; } vise[id]=1; int v=nw^ar[id]^br[id]; tp^=1; dfs(v); } } signed main(){ cin>>n>>K; int ftot=0; for(int i=1;i<=n+n;i++){ int a;int b;int c; cin>>a>>b>>c; b+=n; ar[i]=a;br[i]=b;cr[i]=c; ftot+=c; dgr[a]++; dgr[b]++; e[a].push_back(i); e[b].push_back(i); } for(int i=1;i<=n+n;i++){ if(dgr[i]==0){ cout<<"NO\n";return 0; } } queue<int>q; for(int i=1;i<=n+n;i++){ if(dgr[i]==1){ q.push(i); vise[e[i][0]]=1; if( i<=n ){ basea+=cr[e[i][0]]; } vis[i]=1; } } while(q.size()){ int nw=q.front(); q.pop(); vis[nw]=1; for(int i=0;i<e[nw].size();i++){ int id=e[nw][i]; if(vise[id]){continue;} int v=ar[i]^br[i]^nw; dgr[v]--; if(dgr[v]==1){ for(int j=0;j<e[v].size();j++){ int idd=e[v][j]; if(vise[idd]){continue;} if(v<=n){ basea+=cr[idd]; } vise[idd]=1; } q.push(v); } } }/* cout<<basea<<"\n"; for(int i=1;i<=n+n;i++){ cout<<vis[i]<<" "; }cout<<endl; for(int i=1;i<=n+n;i++){ cout<<vise[i]<<" "; }*/ vector<pair<int,int>>vc; for(int i=1;i<=n;i++){ if(vis[i]){continue;} tota=0; totb=0; tp=0; dfs(i); vc.push_back({tota,totb}); } dp[basea]=1; for(int i=0;i<vc.size();i++){ dp2=(dp<<vc[i].first); dp2=(dp2|(dp<<vc[i].second)); swap(dp,dp2); dp2=zer; } for(int i=0;i<=n*20;i++){ if(dp[i]&&(abs(ftot-i-i)<=K)){ cout<<"YES\n";return 0; } } cout<<"NO\n"; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 21596 KB | Output is correct |
2 | Correct | 5 ms | 21596 KB | Output is correct |
3 | Correct | 5 ms | 21596 KB | Output is correct |
4 | Correct | 5 ms | 21592 KB | Output is correct |
5 | Correct | 5 ms | 21596 KB | Output is correct |
6 | Correct | 5 ms | 21596 KB | Output is correct |
7 | Correct | 5 ms | 21440 KB | Output is correct |
8 | Correct | 5 ms | 21592 KB | Output is correct |
9 | Correct | 5 ms | 21596 KB | Output is correct |
10 | Correct | 5 ms | 21592 KB | Output is correct |
11 | Correct | 5 ms | 21476 KB | Output is correct |
12 | Correct | 5 ms | 21596 KB | Output is correct |
13 | Correct | 5 ms | 21592 KB | Output is correct |
14 | Correct | 5 ms | 21592 KB | Output is correct |
15 | Correct | 5 ms | 21596 KB | Output is correct |
16 | Correct | 5 ms | 21596 KB | Output is correct |
17 | Correct | 6 ms | 21596 KB | Output is correct |
18 | Correct | 5 ms | 21596 KB | Output is correct |
19 | Correct | 5 ms | 21596 KB | Output is correct |
20 | Correct | 5 ms | 21596 KB | Output is correct |
21 | Correct | 5 ms | 21592 KB | Output is correct |
22 | Correct | 6 ms | 25692 KB | Output is correct |
23 | Correct | 5 ms | 25692 KB | Output is correct |
24 | Correct | 5 ms | 21596 KB | Output is correct |
25 | Correct | 5 ms | 21596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 21596 KB | Output is correct |
2 | Correct | 5 ms | 21596 KB | Output is correct |
3 | Correct | 5 ms | 21596 KB | Output is correct |
4 | Correct | 5 ms | 21592 KB | Output is correct |
5 | Correct | 5 ms | 21596 KB | Output is correct |
6 | Correct | 5 ms | 21596 KB | Output is correct |
7 | Correct | 5 ms | 21440 KB | Output is correct |
8 | Correct | 5 ms | 21592 KB | Output is correct |
9 | Correct | 5 ms | 21596 KB | Output is correct |
10 | Correct | 5 ms | 21592 KB | Output is correct |
11 | Correct | 5 ms | 21476 KB | Output is correct |
12 | Correct | 5 ms | 21596 KB | Output is correct |
13 | Correct | 5 ms | 21592 KB | Output is correct |
14 | Correct | 5 ms | 21592 KB | Output is correct |
15 | Correct | 5 ms | 21596 KB | Output is correct |
16 | Correct | 5 ms | 21596 KB | Output is correct |
17 | Correct | 6 ms | 21596 KB | Output is correct |
18 | Correct | 5 ms | 21596 KB | Output is correct |
19 | Correct | 5 ms | 21596 KB | Output is correct |
20 | Correct | 5 ms | 21596 KB | Output is correct |
21 | Correct | 5 ms | 21592 KB | Output is correct |
22 | Correct | 6 ms | 25692 KB | Output is correct |
23 | Correct | 5 ms | 25692 KB | Output is correct |
24 | Correct | 5 ms | 21596 KB | Output is correct |
25 | Correct | 5 ms | 21596 KB | Output is correct |
26 | Correct | 59 ms | 21848 KB | Output is correct |
27 | Correct | 13 ms | 21816 KB | Output is correct |
28 | Correct | 62 ms | 21852 KB | Output is correct |
29 | Correct | 14 ms | 21596 KB | Output is correct |
30 | Correct | 56 ms | 21852 KB | Output is correct |
31 | Correct | 13 ms | 21596 KB | Output is correct |
32 | Correct | 57 ms | 21852 KB | Output is correct |
33 | Correct | 14 ms | 21592 KB | Output is correct |
34 | Correct | 11 ms | 21596 KB | Output is correct |
35 | Correct | 13 ms | 21596 KB | Output is correct |
36 | Correct | 57 ms | 21832 KB | Output is correct |
37 | Correct | 13 ms | 21596 KB | Output is correct |
38 | Correct | 55 ms | 21732 KB | Output is correct |
39 | Correct | 16 ms | 21596 KB | Output is correct |
40 | Correct | 57 ms | 21848 KB | Output is correct |
41 | Correct | 15 ms | 21596 KB | Output is correct |
42 | Correct | 60 ms | 21852 KB | Output is correct |
43 | Correct | 14 ms | 21592 KB | Output is correct |
44 | Correct | 57 ms | 21852 KB | Output is correct |
45 | Correct | 14 ms | 21596 KB | Output is correct |
46 | Correct | 58 ms | 21852 KB | Output is correct |
47 | Correct | 6 ms | 21596 KB | Output is correct |
48 | Correct | 33 ms | 25864 KB | Output is correct |
49 | Incorrect | 33 ms | 25692 KB | Output isn't correct |
50 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 274 ms | 24800 KB | Output is correct |
2 | Correct | 16 ms | 24156 KB | Output is correct |
3 | Correct | 266 ms | 24800 KB | Output is correct |
4 | Correct | 16 ms | 24152 KB | Output is correct |
5 | Correct | 267 ms | 24796 KB | Output is correct |
6 | Correct | 16 ms | 24152 KB | Output is correct |
7 | Correct | 271 ms | 24800 KB | Output is correct |
8 | Correct | 18 ms | 24156 KB | Output is correct |
9 | Correct | 265 ms | 24888 KB | Output is correct |
10 | Correct | 16 ms | 24152 KB | Output is correct |
11 | Correct | 264 ms | 24800 KB | Output is correct |
12 | Correct | 16 ms | 24156 KB | Output is correct |
13 | Correct | 268 ms | 24844 KB | Output is correct |
14 | Correct | 262 ms | 24796 KB | Output is correct |
15 | Correct | 18 ms | 24156 KB | Output is correct |
16 | Correct | 283 ms | 24796 KB | Output is correct |
17 | Correct | 16 ms | 24156 KB | Output is correct |
18 | Correct | 274 ms | 24800 KB | Output is correct |
19 | Correct | 17 ms | 24112 KB | Output is correct |
20 | Correct | 262 ms | 24800 KB | Output is correct |
21 | Correct | 15 ms | 24016 KB | Output is correct |
22 | Correct | 144 ms | 28704 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 21596 KB | Output is correct |
2 | Correct | 5 ms | 21596 KB | Output is correct |
3 | Correct | 5 ms | 21596 KB | Output is correct |
4 | Correct | 5 ms | 21592 KB | Output is correct |
5 | Correct | 5 ms | 21596 KB | Output is correct |
6 | Correct | 5 ms | 21596 KB | Output is correct |
7 | Correct | 5 ms | 21440 KB | Output is correct |
8 | Correct | 5 ms | 21592 KB | Output is correct |
9 | Correct | 5 ms | 21596 KB | Output is correct |
10 | Correct | 5 ms | 21592 KB | Output is correct |
11 | Correct | 5 ms | 21476 KB | Output is correct |
12 | Correct | 5 ms | 21596 KB | Output is correct |
13 | Correct | 5 ms | 21592 KB | Output is correct |
14 | Correct | 5 ms | 21592 KB | Output is correct |
15 | Correct | 5 ms | 21596 KB | Output is correct |
16 | Correct | 5 ms | 21596 KB | Output is correct |
17 | Correct | 6 ms | 21596 KB | Output is correct |
18 | Correct | 5 ms | 21596 KB | Output is correct |
19 | Correct | 5 ms | 21596 KB | Output is correct |
20 | Correct | 5 ms | 21596 KB | Output is correct |
21 | Correct | 5 ms | 21592 KB | Output is correct |
22 | Correct | 6 ms | 25692 KB | Output is correct |
23 | Correct | 5 ms | 25692 KB | Output is correct |
24 | Correct | 5 ms | 21596 KB | Output is correct |
25 | Correct | 5 ms | 21596 KB | Output is correct |
26 | Correct | 59 ms | 21848 KB | Output is correct |
27 | Correct | 13 ms | 21816 KB | Output is correct |
28 | Correct | 62 ms | 21852 KB | Output is correct |
29 | Correct | 14 ms | 21596 KB | Output is correct |
30 | Correct | 56 ms | 21852 KB | Output is correct |
31 | Correct | 13 ms | 21596 KB | Output is correct |
32 | Correct | 57 ms | 21852 KB | Output is correct |
33 | Correct | 14 ms | 21592 KB | Output is correct |
34 | Correct | 11 ms | 21596 KB | Output is correct |
35 | Correct | 13 ms | 21596 KB | Output is correct |
36 | Correct | 57 ms | 21832 KB | Output is correct |
37 | Correct | 13 ms | 21596 KB | Output is correct |
38 | Correct | 55 ms | 21732 KB | Output is correct |
39 | Correct | 16 ms | 21596 KB | Output is correct |
40 | Correct | 57 ms | 21848 KB | Output is correct |
41 | Correct | 15 ms | 21596 KB | Output is correct |
42 | Correct | 60 ms | 21852 KB | Output is correct |
43 | Correct | 14 ms | 21592 KB | Output is correct |
44 | Correct | 57 ms | 21852 KB | Output is correct |
45 | Correct | 14 ms | 21596 KB | Output is correct |
46 | Correct | 58 ms | 21852 KB | Output is correct |
47 | Correct | 6 ms | 21596 KB | Output is correct |
48 | Correct | 33 ms | 25864 KB | Output is correct |
49 | Incorrect | 33 ms | 25692 KB | Output isn't correct |
50 | Halted | 0 ms | 0 KB | - |