Submission #892894

#	Time	Username	Problem	Language	Result	Execution time	Memory
892894		Jxsh28	Trampoline (info1cup20_trampoline)	C++17	0 / 100	1012 ms	1048576 KiB

trampoline

// Союз нерушимый республик свободных
// Сплотила навеки Великая Русь.
// Да здравствует созданный волей народов
// Единый, могучий Советский Союз!
// Славься, Отечество наше свободное,
// Дружбы народов надёжный оплот!
// Знамя советское, знамя народное
// Пусть от победы к победе ведёт!
// Сквозь грозы сияло нам солнце свободы,
// И Ленин великий нам путь озарил:
// вырастил Сталин — на верность народу,
// труд и на подвиги нас вдохновил!
// Славься, Отечество наше свободное,
// Счастья народов надёжный оплот!
// Знамя советское, знамя народное
// Пусть от победы к победе ведёт!
// Мы армию нашу растили в сраженьях.
// Захватчиков подлых с дороги сметём!
// Мы в битвах решаем судьбу поколений,
// Мы к славе Отчизну свою поведём!
// Славься, Отечество наше свободное,
// Славы народов надёжный оплот!
//Знамя советское, знамя народное
//Пусть от победы к победе ведёт!
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define inf 0x3f3f3f3f
#define pi pair<long long int,long long int>
#define pq priority_queue
#define gcd(x,y) __gcd( x, y)
#define ALL(x) x.begin(),x.end()
#define pll pair<long long,long long>
#define debug(x) cerr<<#x<<':'<<x<<endl
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define INTMAX 2147483647
#define INT_MAX LONG_LONG_MAX
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; //upper_bound and lower_bound swap functions in multi
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set_ll;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset_ll;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
template<class K,class V> using ht = gp_hash_table<K,V,hash<K>,equal_to<K>,direct_mask_range_hashing<>,linear_probe_fn<>,hash_standard_resize_policy<hash_exponential_size_policy<>,hash_load_check_resize_trigger<>,true>>;
// scem unordered_map and unordered_set, to use umap use ht<ll,ll>, emplace doesnt exist so use .insert(), .reserve() is .resize(),  to declare uset is ht<ll,null_type>, all other operations are same as regular

void solve() {
    ll r, c, gn, a, b, cc, d, t; 
    cin >> r >> c >> gn;
    ll visited[r+1][c+1];
    ll color[r+1][c+1];
    memset(color, 0, sizeof(color)); // 1 means green, 0 means blue
    for (ll q = 0; q < gn; q++) {
        cin >> a >> b;
        color[a][b] = 1;
    }
    cin >> t;
    for (ll q = 0; q < t; q++) {
        cin >> a >> b >> cc >> d;
        memset(visited, -1, sizeof(visited));
        queue<pll> bfs;
        bfs.push(MP(b, a));
        visited[b][a] = 1;
        while(!bfs.empty()) {
            ll x = bfs.front().first; 
            ll y = bfs.front().second;
            bfs.pop();
            visited[y][x] = 1;
            if (color[y][x] == 0) {// blue
                if (visited[y][x+1] == -1 && x+1 <= r) {
                    bfs.push(MP(x+1, y));
                    visited[y][x+1] = 1;
                }
            } else { //green
                if (visited[y+1][x] == -1 && y+1 <= c) {
                    bfs.push(MP(x, y+1));
                    visited[y+1][x] = 1;
                }
                if (visited[y][x+1] == -1 && x+1 <= r) {
                    bfs.push(MP(x+1, y));
                    visited[y][x+1] = 1;
                }
            }
        }
        // for (ll q = 1; q <= r; q++) {
        //     for (ll w = 1; w <= c; w++) {
        //         cout << color[q][w] << " " ;
        //     } 
        //     cout << "\n";
        // }
        // for (ll q = 1; q <= r; q++) {
        //     for (ll w = 1; w <= c; w++) {
        //         cout << visited[q][w] << " " ;
        //     } 
        //     cout << "\n";
        // }
        if (visited[cc][d] == 1) {
            cout << "Yes" << "\n";
        } else {
            cout << "No" << "\n";
        }
    }
}

signed main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);
  ll tc=1;
  //cin >> tc;
  for (ll q = 0; q < tc; q++) {solve();}
}

Compilation message (stderr)

trampoline.cpp:50: warning: "INT_MAX" redefined
   50 | #define INT_MAX LONG_LONG_MAX
      | 
In file included from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from trampoline.cpp:25:
/usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:120: note: this is the location of the previous definition
  120 | #define INT_MAX __INT_MAX__
      |

• Subtask 1: 0 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 27