Submission #366992

#TimeUsernameProblemLanguageResultExecution timeMemory
366992gmyuTug of War (BOI15_tug)C++14
71 / 100
1540 ms12780 KiB
/* ID: USACO_template LANG: C++ PROG: https://oj.uz/problem/view/BOI15_tug */ #include <iostream> //cin , cout #include <fstream> //fin, fout #include <stdio.h> // scanf , pringf #include <cstdio> #include <algorithm> // sort , stuff #include <stack> // stacks #include <queue> // queues #include <map> #include <string> #include <string.h> #include <set> #include <bitset> using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; /// adjlist without weight typedef vector<pii> vii; /// adjlist with weight typedef vector<pair<int,pii>> vpip; /// edge with weight typedef long long ll; #define mp make_pair #define ff first #define ss second #define pb push_back #define sz(x) (int)(x).size() #define adjread {int a, b; cin >> a >> b; adjlist[a].pb(b); adjlist[b].pb(a); } const int MOD = 1e9+7; // 998244353; const int MX = 2e5+5; // const ll INF = 1e18; // #define MAXV 30007 #define MAXE 100007 const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions struct NODE { int x, y; int val; int visited; bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); } }; struct EDGE { int from, to; ll weight; bool operator<(EDGE other) const { return weight < other.weight; } }; bool debug; int N, Klim; vii adjlist[2][MAXV]; int marked[2][MAXV]; int s[2*MAXV]; int d0; int roomCt; int roomID[2][MAXV]; vii room[MAXV]; int deltaroom[MAXV]; void floodfill(int j, int i) { if(roomID[j][i] != 0) return; roomID[j][i] = roomCt; room[roomCt].pb(mp(j, i)); for(auto x : adjlist[j][i]) { floodfill((j+1)%2, x.ff); } } int visited[2][MAXV]; int floodcal(int rm, pii v, int sel, int vis) { if(visited[v.ff][v.ss] == vis) return 0; visited[v.ff][v.ss] = vis; int d = adjlist[v.ff][v.ss][sel].ss * ( (v.ff==0)? 1 : (-1)); if(debug) cout << v.ff << "," << v.ss << " assigned " << d << endl; int j1 = (v.ff+1)%2, i1 = adjlist[v.ff][v.ss][(sel+1)%2].ff; int sel1; if(adjlist[j1][i1][0].ff == v.ss && adjlist[j1][i1][0].ss == adjlist[v.ff][v.ss][(sel+1)%2].ss ) sel1 = 0; else sel1 = 1; d += floodcal(rm, mp(j1, i1), sel1, vis); return d; } int main() { debug = false; ios_base::sync_with_stdio(false); cin.tie(0); int i, j, k; int ans = 0; cin >> N >> Klim; for(i=1;i<=2*N;i++) { int a, b, c; cin >> a >> b >> c; adjlist[0][a].pb(mp(b,c)); adjlist[1][b].pb(mp(a,c)); } /// remove single points bool hasSingle = true; while(hasSingle) { hasSingle = false; for(i=1; i<=N;i++) { for(j=0;j<2;j++) { if(marked[j][i]) continue; if(sz(adjlist[j][i])==0) {cout << "NO" << endl; exit(0);} if(sz(adjlist[j][i])==1) { marked[j][i] = 1; d0 += adjlist[j][i][0].ss * ((j==0)? 1 : (-1) ); int j1 = (j+1)%2, i1 = adjlist[j][i][0].ff; for(k=0; k<sz(adjlist[j1][i1]) && adjlist[j1][i1][k].ff !=i; k++ ); adjlist[j1][i1].erase(adjlist[j1][i1].begin()+k); hasSingle=true; if(debug) cout << j << " " << i << " is single " << endl; } } } } /// assign cycle for(i=1;i<=N;i++) for(j=0;j<2;j++) { if(marked[j][i]) continue; if(roomID[j][i] != 0) continue; roomCt++; floodfill(j, i); } for(i=1; i<= roomCt; i++) { if(debug) cout << endl << "room " << i << endl; int d1 = floodcal(i, room[i][0], 0, 1); int d2 = floodcal(i, room[i][0], 1, 2); d0 += d1; deltaroom[i] = d2 - d1; } /// DP the assignment bitset<1200007> dp; int offset = 60001; dp[offset+d0]=1; if(debug) cout << d0 << endl; for(i=1;i<=roomCt;i++) { if(debug) cout << deltaroom[i] << endl; if(deltaroom[i]>=0) dp |= (dp << deltaroom[i]); else dp |= (dp >> (-deltaroom[i])); } for(i=0;i<=Klim;i++) if(dp[offset+i]==1 | dp[offset-i]==1) {cout << "YES" << endl; exit(0);} cout << "NO" << endl; }

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:150:24: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
  150 |         if(dp[offset+i]==1 | dp[offset-i]==1)  {cout << "YES" << endl; exit(0);}
tug.cpp:94:9: warning: unused variable 'ans' [-Wunused-variable]
   94 |     int ans = 0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...