Submission #84015

#	Time	Username	Problem	Language	Result	Execution time	Memory
84015		ekrem	Port Facility (JOI17_port_facility)	C++98	22 / 100	6086 ms	40812 KiB

port_facility

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define N 1000005
using namespace std;

typedef pair < int , int > ii;

int n, var[N], u[N];
pair < int , int > x[N];
vector < int > g[N];
long long ans = 1;

void bfs(int node){
	ans = ans*2%mod;
	u[node] = 1;
	queue < ii > q;
	q.push(mp(node, 0) );
	while(!q.empty()){
		int node = q.front().st;
		int par = q.front().nd;
		q.pop();
		for(int i = 0; i < g[node].size(); i++)
			if(g[node][i] != par){
				if(u[g[node][i]] == 0){
					q.push(mp(g[node][i], node));
					u[g[node][i]] = 3 - u[node];
				}
				else if(u[g[node][i]] != 3 - u[node]){
					puts("0");
					exit(0);
				}
			}
	}
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
		scanf("%d %d",&x[i].st ,&x[i].nd);
	sort(x + 1, x + n + 1);
	for(int i = 1; i <= n; i++)
		for(int j = i + 1; j <= n; j++)
			if(i != j and x[j].st < x[i].nd and x[j].nd > x[i].nd){
				g[i].pb(j);
				g[j].pb(i);
				// cout << i << " " << j << endl;
			}
	for(int i = 1; i <= n; i++)
		if(!u[i]){
			bfs(i);
		}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void bfs(int)':
port_facility.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < g[node].size(); i++)
                  ~~^~~~~~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
port_facility.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x[i].st ,&x[i].nd);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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