Submission #892935

#	Time	Username	Problem	Language	Result	Execution time	Memory
892935		Jxsh28	Trampoline (info1cup20_trampoline)	C++17	23 / 100	1004 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));
            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 <= c) {
                        bfs.push(MP(x+1, y));
                        visited[y][x+1] = 1;
                    }
                } else { //green
                    if (visited[y+1][x] == -1 && y+1 <= r) {
                        bfs.push(MP(x, y+1));
                        visited[y+1][x] = 1;
                    }
                    if (visited[y][x+1] == -1 && x+1 <= c) {
                        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: 23 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 27