Submission #34398

#TimeUsernameProblemLanguageResultExecution timeMemory
34398imaxblueFile Paths (BOI15_fil)C++14
33 / 100
499 ms4664 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define x first #define y second #define pii pair<int, int> #define p3i pair<pii, int> #define pll pair<ll, ll> #define p3l pair<pll, ll> #define lseg L, (L+R)/2, N*2+1 #define rseg (L+R)/2+1, R, N*2+2 #define ub upper_bound #define lb lower_bound #define pq priority_queue #define MN 1000000007 #define fox(k, x) for (int k=0; k<x; ++k) #define fox1(k, x) for (int k=1; k<=x; ++k) #define foxr(k, x) for (int k=x-1; k>=0; --k) #define fox1r(k, x) for (int k=x; k>0; --k) #define ms multiset #define flood(x) memset(x, 0x3f3f3f3f, sizeof x) #define drain(x) memset(x, 0, sizeof x) #define rng() (rand() >> 3)*rand() int n, m, k, t, a, b; ll d[6005]; vector<pii> v[6005], w; vector<ll> s; vector<int> cyc; vector<int> f[6005]; bool p[1000005], win[1000005], u[3005]; void factor(int P, ll D){ for(int l=1; 1LL*l*l<=D; ++l){ if (D%l==0){ f[P].pb(l); f[P].pb(D/l); } } } void dfs2(int N, ll D){ fox(l, v[N].size()){ dfs2(v[N][l].x, D+v[N][l].y); } if (N<=n && D+t<=k) p[D+t]=1; } void dfs3(int N, ll D){ fox(l, v[N].size()){ dfs3(v[N][l].x, D+v[N][l].y); } if (N>n && !u[N] && d[N]<=k){ w.pb(mp(k-d[N], N)); } else if (D+t<=k){ cyc.pb(D+t); } } void dfs(int N, ll D){ if (N>n){ d[N]=D; //cout << N << ' ' << D << endl; //fox(l, s.size()) cout << s[l] << ' '; cout << endl; if (D==k){ u[N-n]=1; return; } fox(l, s.size()) if (D-s[l]<=k && p[k-(D-s[l])]){ u[N-n]=1; return; } if ((k-D)>=0 && (k-D)%(t)==0){ u[N-n]=1; return; } if (D<=k) factor(N, k-D); return; } s.pb(D); fox(l, v[N].size()){ dfs(v[N][l].x, D+v[N][l].y); } s.pop_back(); w.clear(); cyc.clear(); dfs3(N, 0); sort(w.begin(), w.end()); fox(l, cyc.size()){ win[cyc[l]]=1; } fox(l, w.size()){ if (l>0 && w[l].x==w[l-1].x){ if (u[w[l-1].y]) u[w[l].y]=1; continue; } fox(l2, f[w[l].y].size()){ if (win[f[w[l].y][l2]]){ u[w[l].y]=1; } } } fox(l, cyc.size()){ win[cyc[l]]=0; } } int main(){ cin >> n >> m >> k >> t; ++t; fox1(l, n){ cin >> a >> b; v[a].pb(mp(l, b+1)); } fox1(l, m){ cin >> a >> b; v[a].pb(mp(l+n, b+1)); } dfs2(0, 0); dfs(0, 0); fox1(l, m){ if (u[l]) cout << "YES\n"; else cout << "NO\n"; } return 0; }

Compilation message (stderr)

fil.cpp: In function 'void dfs2(int, long long int)':
fil.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
fil.cpp:43:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^
fil.cpp: In function 'void dfs3(int, long long int)':
fil.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
fil.cpp:50:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^
fil.cpp: In function 'void dfs(int, long long int)':
fil.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
fil.cpp:67:9: note: in expansion of macro 'fox'
         fox(l, s.size())
         ^
fil.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
fil.cpp:78:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^
fil.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
fil.cpp:85:5: note: in expansion of macro 'fox'
     fox(l, cyc.size()){
     ^
fil.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
fil.cpp:88:5: note: in expansion of macro 'fox'
     fox(l, w.size()){
     ^
fil.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
fil.cpp:93:9: note: in expansion of macro 'fox'
         fox(l2, f[w[l].y].size()){
         ^
fil.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
fil.cpp:99:5: note: in expansion of macro 'fox'
     fox(l, cyc.size()){
     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...