제출 #45564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45564		eropsergeev	Port Facility (JOI17_port_facility)	C++14	22 / 100	6027 ms	18044 KiB

port_facility

#ifdef LOCKAL
    #define _GLIBCXX_DEBUG
#endif
#ifndef LOCKAL
    #pragma GCC optimize("Ofast")
    #pragma GCC target("sse3,sse4")
#endif
#include <bits/stdc++.h>
//#define TIMUS
//#define FILENAME "journey"
#ifndef TIMUS
    #include <ext/rope>
    #include <ext/pb_ds/assoc_container.hpp>
#endif // TIMUS
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int INF = INT_MAX / 2;
const ll LINF = (ll)2e18 + 666, M = 1e9 + 7;
const ld EPS = 1e-7;

#ifndef M_PI
    const ld M_PI = acos(-1);
#endif // M_PI

using namespace std;

#ifndef TIMUS
    using namespace __gnu_cxx;
    using namespace __gnu_pbds;

    template<class K, class T>
    using ordered_map = tree<K, T, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

    template<class T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif

void run();

template<class T1, class T2>
inline bool mini(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

template<class T1, class T2>
inline bool maxi(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}

int main()
{
    #ifndef LOCKAL
        #ifdef FILENAME
            freopen(FILENAME".in", "r", stdin);
            freopen(FILENAME".out", "w", stdout);
        #endif // FILENAME
    #endif
    #ifndef TIMUS
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif // TIMUS
    srand(time(0));
    auto start = clock();
    run();
    #ifdef LOCKAL
        //cout << endl;
        cout << "\ntime = " << (ld)(clock() - start) / CLOCKS_PER_SEC << "\n";
    #endif
    return 0;
}

#define DEBUG
#if defined DEBUG && defined LOCKAL
    #define debugdo(x) x
#else
    #define debugdo(x)
#endif

#define debug(x) debugdo(cout << x << endl)
#define debug2(x) debugdo(cout << x << " ")

// ---SOLUTION--- //

vector<vector<int>> g;
vector<char> use;

void dfs(int v, char c = 1)
{
    use[v] = c;
    for (auto x: g[v])
    {
        if (!use[x])
            dfs(x, c ^ 3);
        else if (use[x] == use[v])
        {
            cout << 0;
            exit(0);
        }
    }
}

void run()
{
    int n;
    cin >> n;
    vector<int> e(n * 2), ap(n), bp(n);
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        e[a - 1] = i + 1;
        e[b - 1] = -i - 1;
        ap[i] = a - 1;
        bp[i] = b - 1;
    }
    g.resize(n);
    use.resize(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = ap[i] + 1; j < bp[i]; j++)
        {
            //debug(i << " " << j << " " << e[j]);
            if (e[j] > 0)
            {
                if (bp[e[j] - 1] > bp[i])
                {
                    //debug(i + 1 << " " << e[j]);
                    g[i].pb(e[j] - 1);
                    g[e[j] - 1].pb(i);
                }
            }
        }
    }
    ll ans = 1;
    for (int i = 0; i < n; i++)
    {
        if (!use[i])
        {
            dfs(i);
            ans <<= 1;
            ans %= M;
        }
    }
    cout << ans;
}
/*

*/

컴파일 시 표준 에러 (stderr) 메시지

port_facility.cpp: In function 'int main()':
port_facility.cpp:84:10: warning: unused variable 'start' [-Wunused-variable]
     auto start = clock();
          ^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22