oj.uz

Submission #744878

# Submission time Handle Problem Language Result Execution time Memory
744878 2023-05-19T07:23:00 Z Nahian9696 Game (APIO22_game) C++17
30 / 100
 1656 ms 262144 KB 
#include "game.h"

#include <iostream>
#include <iomanip>

#include <cmath>
#include <cstring>
#include <algorithm>


#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <string>
#include <vector>
#include <bitset>

using namespace std;


typedef long double                         ld;
typedef long long                           ll;
typedef vector<int32_t>                     vi;
typedef vector<ll>                          vll;
typedef pair<int32_t, int32_t>              pii;



#define endl                                "\n"
#define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
#define f1(i,n)                             for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r)                         for(int32_t i=(l); i <  (r); i++)
#define rep1(i,l,r)                         for(int32_t i=(l); i <= (r); i++)

#define all(x)                              (x).begin(), (x).end()
#define rall(x)                             (x).rbegin(), (x).rend()
#define asrt(v)                             sort(all(v))
#define dsrt(v)                             sort(rall(v))
#define revStr(str)                         string(rall(str))
#define len(a)                              ((int64_t)(a).size())
#define front_zero(n)                       __builtin_clzll(n)
#define back_zero(n)                        __builtin_ctzll(n)
#define total_one(n)                        __builtin_popcountll(n)
#define lcm(a, b)                           (((a)*(b))/gcd(a,b))
#define mem(a, b)                           memset(a, b, sizeof(a))

#define pb                                  push_back
#define pf                                  push_front
#define mp                                  make_pair
#define ff                                  first
#define ss                                  second

#define finish                              return 0
#define clean                               fflush(stdout)

#define Inf                                 (int32_t)(1e9)
#define INF                                 (lli)(1e18)
#define Eps                                 (ld)(1e-9)
#define EPS                                 (ld)(1e-18)
#define PI                                  (ld)(3.141592653589793238462643383279502884197169L)
#define MOD                                 (int32_t)(1e9+7)
#define MXN                                 (int32_t)(1e5+7)




template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline void printarr(dataType* arr, int32_t n) {f0(i,n) cout << arr[i] << " "; cout << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}



short n, k;
vector<short> grph[30005], invgrph[30005];
// bool fr[30005][1003], t[30005][1003];
set<short> from[30005], to[30005];





void init(int N, int K) {
    n = N;
    k = K;
}

int add_teleporter(int u, int v) {
    // print(n, k);
    if((u < k) && (v < k)) {
        // print("Ok");
        if(u == v) return 1;
        if(u > v) {
            // print(u, v, "u < v");
            return 1;
        }
        else return 0;
    }

    if(u == v) return 0;

    if(u < k) {
        if(to[v].size()) {
            short mn = *(to[v].begin());
            if(mn <= u) return 1;
        }


        auto it = from[v].find(u);
        if(it == from[v].end()) {
            queue<short> q;
            q.push(v);
            while(!q.empty()) {
                short cur = q.front();
                q.pop();

                from[cur].insert(u);
                for(short nxt: grph[cur]) {
                    if(nxt < k) continue;
                    auto it = from[nxt].find(u);
                    if(it == from[nxt].end()) {
                        q.push(nxt);
                    }
                }
            }
        }

        

        grph[u].pb(v);
        invgrph[v].pb(u);
    }


    if(v < k) {
        if(from[u].size()) {
            short mx = *prev(from[u].end());
            if(mx >= v) return 1;
        }

        auto it = to[u].find(v);
        if(it == to[u].end()) {
            queue<short> q;
            q.push(u);
            while(!q.empty()) {
                short cur = q.front();
                q.pop();

                to[cur].insert(v);
                for(short nxt: invgrph[cur]) {
                    if(nxt < k) continue;
                    auto it = to[nxt].find(v);
                    if(it == to[nxt].end()) {
                        q.push(nxt);
                    }
                }
            }
        }


        grph[u].pb(v);
        invgrph[v].pb(u);
    }


    // int U = u, V = v;

    for(short uu: from[u]) {
        if(to[v].size()) {
            short mn = *(to[v].begin());
            if(mn <= uu) return 1;
        }


        auto it = from[v].find(uu);
        if(it == from[v].end()) {
            queue<short> q;
            q.push(v);
            while(!q.empty()) {
                short cur = q.front();
                q.pop();

                from[cur].insert(uu);
                for(short nxt: grph[cur]) {
                    if(nxt < k) continue;
                    auto it = from[nxt].find(uu);
                    if(it == from[nxt].end()) {
                        q.push(nxt);
                    }
                }
            }
        }
    }

    for(short vv: to[v]) {
        if(from[u].size()) {
            short mx = *prev(from[u].end());
            if(mx >= vv) return 1;
        }

        auto it = to[u].find(vv);
        if(it == to[u].end()) {
            queue<short> q;
            q.push(u);
            while(!q.empty()) {
                short cur = q.front();
                q.pop();

                to[cur].insert(vv);
                for(short nxt: invgrph[cur]) {
                    if(nxt < k) continue;
                    auto it = to[nxt].find(vv);
                    if(it == to[nxt].end()) {
                        q.push(nxt);
                    }
                }
            }
        }
    }

    grph[u].pb(v);
    invgrph[v].pb(u);


    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 2 ms 4432 KB Output is correct
10 Correct 2 ms 4432 KB Output is correct
11 Correct 3 ms 4432 KB Output is correct
12 Correct 2 ms 4432 KB Output is correct
13 Correct 2 ms 4432 KB Output is correct
14 Correct 3 ms 4560 KB Output is correct
15 Correct 3 ms 4560 KB Output is correct
16 Correct 3 ms 4492 KB Output is correct
17 Correct 3 ms 4560 KB Output is correct
18 Correct 2 ms 4544 KB Output is correct
19 Correct 3 ms 4432 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 2 ms 4432 KB Output is correct
10 Correct 2 ms 4432 KB Output is correct
11 Correct 3 ms 4432 KB Output is correct
12 Correct 2 ms 4432 KB Output is correct
13 Correct 2 ms 4432 KB Output is correct
14 Correct 3 ms 4560 KB Output is correct
15 Correct 3 ms 4560 KB Output is correct
16 Correct 3 ms 4492 KB Output is correct
17 Correct 3 ms 4560 KB Output is correct
18 Correct 2 ms 4544 KB Output is correct
19 Correct 3 ms 4432 KB Output is correct
20 Correct 3 ms 4528 KB Output is correct
21 Correct 3 ms 4432 KB Output is correct
22 Correct 3 ms 4560 KB Output is correct
23 Correct 3 ms 4528 KB Output is correct
24 Correct 60 ms 19176 KB Output is correct
25 Correct 53 ms 13616 KB Output is correct
26 Correct 17 ms 6184 KB Output is correct
27 Correct 21 ms 7552 KB Output is correct
28 Correct 8 ms 5712 KB Output is correct
29 Correct 10 ms 5688 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 2 ms 4432 KB Output is correct
10 Correct 2 ms 4432 KB Output is correct
11 Correct 3 ms 4432 KB Output is correct
12 Correct 2 ms 4432 KB Output is correct
13 Correct 2 ms 4432 KB Output is correct
14 Correct 3 ms 4560 KB Output is correct
15 Correct 3 ms 4560 KB Output is correct
16 Correct 3 ms 4492 KB Output is correct
17 Correct 3 ms 4560 KB Output is correct
18 Correct 2 ms 4544 KB Output is correct
19 Correct 3 ms 4432 KB Output is correct
20 Correct 3 ms 4528 KB Output is correct
21 Correct 3 ms 4432 KB Output is correct
22 Correct 3 ms 4560 KB Output is correct
23 Correct 3 ms 4528 KB Output is correct
24 Correct 60 ms 19176 KB Output is correct
25 Correct 53 ms 13616 KB Output is correct
26 Correct 17 ms 6184 KB Output is correct
27 Correct 21 ms 7552 KB Output is correct
28 Correct 8 ms 5712 KB Output is correct
29 Correct 10 ms 5688 KB Output is correct
30 Correct 22 ms 5756 KB Output is correct
31 Correct 8 ms 4916 KB Output is correct
32 Correct 28 ms 7720 KB Output is correct
33 Correct 20 ms 6632 KB Output is correct
34 Runtime error 1656 ms 262144 KB Execution killed with signal 9
35 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 2 ms 4432 KB Output is correct
10 Correct 2 ms 4432 KB Output is correct
11 Correct 3 ms 4432 KB Output is correct
12 Correct 2 ms 4432 KB Output is correct
13 Correct 2 ms 4432 KB Output is correct
14 Correct 3 ms 4560 KB Output is correct
15 Correct 3 ms 4560 KB Output is correct
16 Correct 3 ms 4492 KB Output is correct
17 Correct 3 ms 4560 KB Output is correct
18 Correct 2 ms 4544 KB Output is correct
19 Correct 3 ms 4432 KB Output is correct
20 Correct 3 ms 4528 KB Output is correct
21 Correct 3 ms 4432 KB Output is correct
22 Correct 3 ms 4560 KB Output is correct
23 Correct 3 ms 4528 KB Output is correct
24 Correct 60 ms 19176 KB Output is correct
25 Correct 53 ms 13616 KB Output is correct
26 Correct 17 ms 6184 KB Output is correct
27 Correct 21 ms 7552 KB Output is correct
28 Correct 8 ms 5712 KB Output is correct
29 Correct 10 ms 5688 KB Output is correct
30 Correct 22 ms 5756 KB Output is correct
31 Correct 8 ms 4916 KB Output is correct
32 Correct 28 ms 7720 KB Output is correct
33 Correct 20 ms 6632 KB Output is correct
34 Runtime error 1656 ms 262144 KB Execution killed with signal 9
35 Halted 0 ms 0 KB -