제출 #261682

#제출 시각아이디문제언어결과실행 시간메모리
261682ant101Tug of War (BOI15_tug)C++14
23 / 100
13 ms3328 KiB
#include <bits/stdc++.h> #define fr(i, n, m) for(int i = (n); i < (m); i ++) #define pb push_back #define st first #define nd second #define pq priority_queue #define all(x) begin(x), end(x) #include <time.h> #include <cmath> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const int i_inf = 1e9; const ll inf = 1e18; const ll mod = 1000000007; const ld eps = 1e-13; const ld pi = 3.14159265359; mt19937 _rand(time(NULL)); clock_t timer = clock(); const int mxn = 60005; int n, k; int l[mxn], r[mxn], s[mxn]; vector<int> g[mxn]; int deg[mxn]; int used[mxn]; int vis[mxn]; int nxt(int u, int ed){ return l[ed]^r[ed]^u; } void build(){ fr(i, 0, n){ l[i] = l[i]-1; r[i] = r[i]-1+n/2; } fr(i, 0, n){ g[l[i]].pb(i); g[r[i]].pb(i); ++deg[l[i]]; ++deg[r[i]]; } } void remove(int ed){ used[ed] = 2; --deg[l[ed]], --deg[r[ed]]; } void update(int &sa, int &sb, int u, int ed){ if(u == l[ed]) sa += s[ed]; else sb += s[ed]; } int find_one(int u){ for(auto e : g[u]){ if(used[e] == 2) continue; return e; } } int suma, sumb; void pruning(){ queue<int> Q; fr(i, 0, n) if(deg[i] == 1) Q.push(i); while(!Q.empty()){ int u = Q.front(); Q.pop(); int ed = find_one(u); remove(ed); update(suma, sumb, u, ed); if(deg[nxt(u, ed)] == 1) Q.push(nxt(u,ed)); } } void dfs(int u, int flag, int &sa, int &sb){ for(auto e : g[u]){ if(used[e] == flag) continue; if(vis[nxt(u, e)] == flag){ cout<<"NO"<<endl; exit(0); } used[e] = flag, vis[nxt(u, e)] = flag; update(sa, sb, nxt(u, e), e); dfs(nxt(u, e), flag, sa, sb); } } pii direct_edge(int ed){ int sa1 = s[ed], sb1 = 0; used[ed] = 1, vis[l[ed]] = 1; dfs(l[ed], 1, sa1, sb1); int sa2 = 0, sb2 = s[ed]; used[ed] = 2, vis[r[ed]] = 2; dfs(r[ed], 2, sa2, sb2); return {sa1-sb1, sa2-sb2}; } bitset<20*mxn> dp; void solve(){ cin >> n >> k; n <<= 1; bool sub3 = true; fr(i, 0, n){ cin >> l[i] >> r[i] >> s[i]; if(s[i] != 1) sub3 = false; } build(); pruning(); vector<pii> v; fr(i, 0, n){ if(used[i] == 2) continue; v.pb(direct_edge(i)); } if(sub3){ cout<<"YES"<<endl; return; } int m = v.size(); dp[20*(n>>1)+suma-sumb] = 1; fr(i, 0, m){ if(v[i].st > 0 && v[i].nd > 0) dp = (dp<<v[i].st)|(dp<<v[i].nd); else if(v[i].st > 0 && v[i].nd < 0) dp = (dp<<v[i].st)|(dp>>(-v[i].nd)); else if(v[i].st < 0 && v[i].nd > 0) dp = (dp>>(-v[i].st))|(dp<<v[i].nd); else dp = (dp>>(-v[i].st))|(dp>>(-v[i].nd)); } fr(i, 0, k+1){ if(dp[20*(n>>1)+i]||dp[20*(n>>1)-i]){ cout<<"YES"<<endl; return; } } cout<<"NO"<<endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }

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

tug.cpp: In function 'int find_one(int)':
tug.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...