Submission #318937

#	Time	Username	Problem	Language	Result	Execution time	Memory
318937		arnold518	Port Facility (JOI17_port_facility)	C++14	22 / 100	6043 ms	41444 KiB

port_facility

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;
const ll MOD = 1e9+7;

int N;
pii A[MAXN+10];
vector<int> adj[MAXN+10];

int vis[MAXN+10];
bool flag=true;

void dfs(int now, int col)
{
	vis[now]=col;
	for(auto nxt : adj[now])
	{
		if(vis[nxt]==0) dfs(nxt, 3-col);
		else if(vis[nxt]!=3-col) flag=false;
	}
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);

	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=N; j++)
		{
			if(i==j) continue;
			if(A[i].first<A[j].first && A[j].first<A[i].second && A[i].second<A[j].second)
			{
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}

	ll ans=1;
	for(int i=1; i<=N; i++)
	{
		if(vis[i]) continue;
		dfs(i, 1);
		ans*=2;
		ans%=MOD;
	}

	if(!flag) printf("0\n");
	else printf("%lld\n", ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
port_facility.cpp:31:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  for(int i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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