Submission #427312

#	Time	Username	Problem	Language	Result	Execution time	Memory
427312		tqbfjotld	Port Facility (JOI17_port_facility)	C++14	22 / 100	6081 ms	43720 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

int val[1000005];
vector<int> adjl[1000005];
const int MOD = 1000000007;

bool dfs(int node){
    for (auto x : adjl[node]){
        //printf("edge %d %d\n",node,x);
        if (val[x]!=-1) {
            if (val[x]==val[node]) return false;
            continue;
        }
        val[x] = 1-val[node];
        if (!dfs(x)) return false;
    }
    return true;
}

int A[1000005];
int B[1000005];

int main(){
    int n;
    scanf("%d",&n);
    for (int x = 0; x<n; x++){
        scanf("%d%d",&A[x],&B[x]);
    }
    for (int x = 0; x<n; x++){
        for (int y = 0; y<x; y++){
            if (A[x]<A[y] && B[x]<B[y] && A[y]<B[x]){
                adjl[x].push_back(y);
                adjl[y].push_back(x);
            }
            if (A[x]>A[y] && B[x]>B[y] && A[x]<B[y]){
                adjl[x].push_back(y);
                adjl[y].push_back(x);
            }
        }
    }
    int ans = 1;
    memset(val,-1,sizeof(val));
    for (int x = 0; x<n; x++){
        if (val[x]==-1){
            val[x] = 0;
            if (dfs(x)){
                ans<<=1;
                ans %= MOD;
            }
            else{
                ans = 0;
            }
        }
    }
    printf("%d",ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
port_facility.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d%d",&A[x],&B[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

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