Submission #1063044

#TimeUsernameProblemLanguageResultExecution timeMemory
1063044AndreyLong Mansion (JOI17_long_mansion)C++14
100 / 100
293 ms48572 KiB
#include<bits/stdc++.h> using namespace std; int n; vector<int> haha[500001]; vector<int> idk(500001); vector<bool> bruh(500001); vector<pair<int,int>> ans(500001); vector<int> roll(0); void troll() { for(int i = 0; i < roll.size(); i++) { bruh[roll[i]] = false; } roll.clear(); } void ins(int a) { for(int v: haha[a]) { bruh[v] = true; roll.push_back(v); } } void dude(int l, int r) { if(l == r) { ans[l] = {l,l}; return; } int mid = (l+r)/2; dude(l,mid); dude(mid+1,r); int ql = mid+1,qr = mid; for(int i = mid+1; i <= r; i++) { if(qr < i) { qr = i; ins(qr); while(true) { if(ql > l && bruh[idk[ql-1]]) { ql--; ins(ql); } else if(qr < r && bruh[idk[qr]]) { qr++; ins(qr); } else { break; } } } if(ans[i].first == mid+1) { ans[i] = {ql,qr}; } } troll(); ql = mid+1,qr = mid; for(int i = mid; i >= l; i--) { if(ql > i) { ql = i; ins(ql); while(true) { if(ql > l && bruh[idk[ql-1]]) { ql--; ins(ql); } else if(qr < r && bruh[idk[qr]]) { qr++; ins(qr); } else { break; } } } if(ans[i].second == mid) { ans[i] = {ql,qr}; } } troll(); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i = 1; i < n; i++) { cin >> idk[i]; } for(int i = 1; i <= n; i++) { int k,a; cin >> k; for(int j = 0; j < k; j++) { cin >> a; haha[i].push_back(a); } } dude(1,n); int q; cin >> q; for(int i = 0; i < q; i++) { int x,y; cin >> x >> y; if(y >= ans[x].first && y <= ans[x].second) { cout << "YES\n"; } else { cout << "NO\n"; } } return 0; }

Compilation message (stderr)

long_mansion.cpp: In function 'void troll()':
long_mansion.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i < roll.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...