Submission #1014998

#TimeUsernameProblemLanguageResultExecution timeMemory
1014998jamjanekGolf (JOI17_golf)C++14
0 / 100
0 ms348 KiB
#include<bits/stdc++.h> using namespace std; struct rect{int a, b, c, d; int id;}; vector<rect>pros; bool cmp1(rect a, rect b){ return a.a < b.a; } bool cmp2(rect a, rect b){ return a.c < b.c; } bool cmp3(rect a, rect b){ return a.b > b.b; } bool cmp4(rect a, rect b){ return a.d > b.d; } struct oX{int x, p, k, id, dist;}; struct oY{int y, p, k, id, dist;}; oX oXs[400010]; oY oYs[400010]; bool przecina(int x, int y){ if(oXs[x].p<=oYs[y].y && oXs[x].k>=oYs[y].y && oYs[y].p<=oXs[x].x && oYs[y].k>=oXs[x].x) return 1; return 0; } const int base = 1<<10; int tree[2*base]; void ustaw(int w, int l, int p, int a, int b, int val){ if(l>b || p<a)return; if(a<=l && p<=b){ tree[w] = val; return; } if(tree[w]!=-1) tree[w*2] = tree[w*2+1] = tree[w]; tree[w] = -1; ustaw(w*2, l, (l+p)/2, a, b, val); ustaw(w*2+1, (l+p)/2+1, p, a, b, val); } int value(int w){ int ans = -1; w+=base; while(w>0){ if(tree[w]!=-1) ans = tree[w]; w/=2; } return ans; } int main() { int sx, sy, tx, ty, n, i; scanf("%d%d%d%d%d", &sx, &sy, &tx, &ty, &n); for(i=0;i<n;i++){ pros.push_back({}); scanf("%d%d%d%d", &pros.back().a, &pros.back().b, &pros.back().c, &pros.back().d); } pros.push_back({sx, sx, sy, sy});//start ma id n pros.push_back({tx, tx, ty, ty});//koniec ma id n+1 for(i=0;i<n+2;i++){ pros[i].id = i; oXs[i*4+0].x = pros[i].a; oYs[i*4+1].y = pros[i].c; oXs[i*4+2].x = pros[i].b; oYs[i*4+3].y = pros[i].d; } sort(pros.begin(), pros.end(), cmp1); ustaw(1, 0, base-1, 0, 2*(n+1), 0); for(auto &ij: pros){ oYs[ij.id*4+1].p = value(ij.c); oYs[ij.id*4+3].p = value(ij.d); ustaw(1, 0, base-1, ij.c+1, ij.d-1, ij.b); } sort(pros.begin(), pros.end(), cmp2); ustaw(1, 0, base-1, 0, 2*(n+1), 0); for(auto &ij: pros){ oXs[ij.id*4+0].p = value(ij.a); oXs[ij.id*4+2].p = value(ij.b); ustaw(1, 0, base-1, ij.a+1, ij.b-1, ij.d); } sort(pros.begin(), pros.end(), cmp3); ustaw(1, 0, base-1, 0, 2*(n+1), 2*(n+1)); for(auto &ij: pros){ oYs[ij.id*4+1].k = value(ij.c); oYs[ij.id*4+3].k = value(ij.d); ustaw(1, 0, base-1, ij.c+1, ij.d-1, ij.a); } sort(pros.begin(), pros.end(), cmp4); ustaw(1, 0, base-1, 0, 2*(n+1), 2*(n+1)); for(auto &ij: pros){ oXs[ij.id*4+0].k = value(ij.a); oXs[ij.id*4+2].k = value(ij.b); ustaw(1, 0, base-1, ij.a+1, ij.b-1, ij.c); } if(sx==tx){ if(oXs[n*4+0].p<=ty && oXs[n*4+0].k>=ty){ printf("1\n");return 0; } } if(sy==ty){ if(oYs[n*4+1].p<=tx && oYs[n*4+1].k>=tx){ printf("1\n");return 0; } } queue<int>kolejka; oXs[n*4+0].dist = 1; oXs[n*4+2].dist = 1; oYs[n*4+1].dist = 1; oYs[n*4+3].dist = 1; kolejka.push(n*4+0); kolejka.push(n*4+1); kolejka.push(n*4+2); kolejka.push(n*4+3); while(kolejka.size()){ auto ij = kolejka.front(); kolejka.pop(); if(ij%2==0){ for(i=1;i<(n+1)*4+4;i+=2){ if(przecina(ij, i) && oYs[i].dist==0){ oYs[i].dist = oXs[ij].dist+1; kolejka.push(i); } } } else{ for(i=0;i<(n+1)*4+4;i+=2){ if(przecina(i, ij) && oXs[i].dist==0){ oXs[i].dist = oYs[ij].dist+1; kolejka.push(i); } } } } printf("%d\n", min({oXs[(n+1)*4+0].dist, oXs[(n+1)*4+2].dist, oYs[(n+1)*4+1].dist, oYs[(n+1)*4+3].dist})); /* printf("X:\n"); for(i=0;i<=(n+1);i++){ printf("%d %d %d %d %d\n", oXs[i*4+0].x, oXs[i*4+0].p, oXs[i*4+0].k, oXs[i*4+0].id, oXs[i*4+0].dist); printf("%d %d %d %d %d\n", oXs[i*4+2].x, oXs[i*4+2].p, oXs[i*4+2].k, oXs[i*4+2].id, oXs[i*4+2].dist); } printf("Y:\n"); for(i=0;i<=(n+1);i++){ printf("%d %d %d %d %d\n", oYs[i*4+1].y, oYs[i*4+1].p, oYs[i*4+1].k, oYs[i*4+1].id, oYs[i*4+1].dist); printf("%d %d %d %d %d\n", oYs[i*4+3].y, oYs[i*4+3].p, oYs[i*4+3].k, oYs[i*4+3].id, oYs[i*4+3].dist); }*/ }

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d%d%d%d%d", &sx, &sy, &tx, &ty, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d%d%d%d", &pros.back().a, &pros.back().b, &pros.back().c, &pros.back().d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...