제출 #744865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744865		Nahian9696	게임 (APIO22_game)	C++17	30 / 100	1470 ms	262144 KiB

game

#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);}



int n, k;
vi grph[30005], invgrph[30005];
// bool fr[30005][1003], t[30005][1003];
set<int> 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()) {
            int mn = *(to[v].begin());
            if(mn <= u) return 1;
        }


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

                from[cur].insert(u);
                for(int 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()) {
            int mx = *prev(from[u].end());
            if(mx >= v) return 1;
        }

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

                to[cur].insert(v);
                for(int 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(int uu: from[u]) {
        if(to[v].size()) {
            int mn = *(to[v].begin());
            if(mn <= uu) return 1;
        }


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

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

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

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

                to[cur].insert(vv);
                for(int 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 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40