Submission #892860

#TimeUsernameProblemLanguageResultExecution timeMemory
892860shoryu386Trampoline (info1cup20_trampoline)C++17
42 / 100
957 ms254800 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define MAXN 100007 vector<int> adj[MAXN]; bitset<MAXN> bs[MAXN]; bool vis[MAXN]; void dfs(int u) { for(int v: adj[u]) { if(!vis[v]) { vis[v] = 1; dfs(v); } bs[u] |= bs[v]; } } main(){ int r, c, n; cin >> r >> c >> n; //r and c are useless lmao int N = 0; map<int, set< pair<int, bool> >> importantPts; int a, b; for (int x = 0; x < n; x++){ cin >> a >> b; importantPts[a].insert({b, 1}); //1 indicating green trampoline importantPts[a+1].insert({b, 0}); N++; N++; } int q; cin >> q; pair<int, int> starts[q], ends[q]; for (int x = 0; x < q; x++){ cin >> starts[x].first >> starts[x].second >> ends[x].first >> ends[x].second; importantPts[ends[x].first].insert({ends[x].second, 0}); N++; } map<pair<int, int>, int> coordToNode; pair<int, int> hmm[N]; int cnt = 0; for (auto y : importantPts){ for (auto z : y.second){ coordToNode[{y.first, z.first}] = cnt; hmm[cnt] = {y.first, z.first}; cnt++; } } for (auto y : importantPts){ //gen DAG pair<int, int> lastCoords = {-1, -1}; for (auto z : y.second){ if (lastCoords.first != -1) adj[coordToNode[lastCoords]].push_back(coordToNode[{y.first, z.first}]); if (z.second){ adj[coordToNode[{y.first, z.first}]].push_back(coordToNode[{y.first+1, z.first}]); } lastCoords = {y.first, z.first}; } } for (int i = 0; i < N; i++) bs[i][i] = 1; for (int i = 0; i < N; i++) { if (vis[i]) continue; vis[i] = 1; dfs(i); } for (int x = 0; x < q; x++){ auto startTramp = importantPts[starts[x].first].lower_bound({starts[x].second, 0}); if (startTramp == importantPts[starts[x].first].end()){ cout << "No\n"; continue; } int startF = starts[x].first, startS = startTramp->first; if (bs[coordToNode[{startF, startS}]][coordToNode[{ends[x].first, ends[x].second}]]){ cout << "Yes\n"; } else cout << "No\n"; } }

Compilation message (stderr)

trampoline.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...