제출 #166994

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

port_facility

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 2e3+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
pii dis[MAXN];
vector<int> adj[MAXN];
int visited[MAXN];
int dfs(int a, int par = -1){
    bool ans = 1;
    for(int i: adj[a]){
        if(i == par) continue;
        if(visited[i] == visited[a]){
            return 0;
        }
        if(visited[i] != 0) continue;
        visited[i] = (visited[a] == 1 ? 2 : 1);
        ans &= dfs(i, a);
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("../IO/int.txt","r",stdin);
        freopen("../IO/out.txt","w",stdout);
    #endif

    cin>>n;

    for(int i = 1; i <= n; i++){
        cin>>dis[i].ff>>dis[i].ss;
    }
    ll ans = 1;
    sort(dis + 1, dis + n + 1);

    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(dis[j].ff < dis[i].ss && dis[j].ss > dis[i].ss){
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    for(int i = 1; i <= n; i++){
        if(visited[i] == 0){
            visited[i] = 1;
            ans *= dfs(i)*2;
            ans %= mod;
        }
    }
    cout<<ans<<endl;
    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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