Submission #353953

#	Time	Username	Problem	Language	Result	Execution time	Memory
353953		arnold518	Mostovi (COI14_mostovi)	C++14	100 / 100	709 ms	45696 KiB

mostovi

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

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

const int MAXN = 1e9;
const int MAXM = 4e5;

int N, M;
int N1, N2;
struct Query
{
	char c; int x, y;
};
Query A[MAXM+10];

vector<int> comp1, comp2;
int par[MAXM+10];

int L[MAXM+10], R[MAXM+10];
set<pii> S[MAXM+10];
set<pii> S1, S2;

void init()
{
	for(int i=1; i<=MAXM; i++)
	{
		par[i]=i;
		L[i]=R[i]=i;
		S[i].clear();
	}
}

int Find(int x)
{
	if(x==par[x]) return x;
	return par[x]=Find(par[x]);
}

void Union(int x, int y)
{
	x=Find(x); y=Find(y);
	assert(x!=y);
	if(S[x].size()>S[y].size()) swap(x, y);
	for(auto it : S[x]) S[y].insert(it);
	S[x].clear();
	par[x]=y;
	L[y]=min(L[y], L[x]);
	R[y]=max(R[x], R[y]);
}

bool solve(int s, int e)
{
	//printf("SOLVE %d %d\n", s, e);
	if(s<=N1 && e>N1)
	{
		int u=Find(s), v=Find(e);
		if(S[u].empty()) return false;
		auto it=S[u].lower_bound(pii(L[v], 0));
		auto jt=S[u].lower_bound(pii(R[v], 2e9));
		if(it==jt) return false;
		jt--;
		int l1, r1, l2, r2;
		l1=it->second; r1=jt->second;
		l2=it->first; r2=jt->first;
		if(r1<s) return false;
		if(r2<e) return false;
		return true;
	}
	if(s>N1 && e<=N1)
	{
		int u=Find(s), v=Find(e);
		if(S[u].empty()) return false;
		auto it=S[u].lower_bound(pii(L[v], 0));
		auto jt=S[u].lower_bound(pii(R[v], 2e9));
		if(it==jt) return false;
		jt--;
		int l1, r1, l2, r2;
		l1=it->second; r1=jt->second;
		l2=it->first; r2=jt->first;
		if(s<l1) return false;
		if(e<l2) return false;
		return true;	
	}
	if(s<=N1 && e<=N1)
	{
		int u=Find(s), v=Find(e);
		if(u<v) return false;
		if(u>v)
		{
			if(S[u].empty()) return false;
			int it=S[u].begin()->first;
			return solve(s, it) && solve(it, e);
		}
		if(u==v)
		{
			if(s<e) return true;
			auto it=S2.lower_bound(pii({s, 0}));
			auto jt=S2.lower_bound(pii({e, 2e9}));
			if(it==S2.end()) return false;
			if(jt==S2.begin()) return false;
			jt--;
			if(Find(it->first)!=u) return false;
			if(Find(jt->first)!=u) return false;
			if(Find(it->second)==Find(jt->second)) return true;
			else return false;
		}
	}
	if(s>N1 && e>N1)
	{
		//printf("HI\n");
		int u=Find(s), v=Find(e);
		if(u>v) return false;
		if(u<v)
		{
			if(S[u].empty()) return false;
			int it=(--S[u].end())->first;
			//printf("%d\n", it);
			return solve(s, it) && solve(it, e);
		}
		if(u==v)
		{
			if(s>e) return true;
			auto it=S1.lower_bound(pii({e, 0}));
			auto jt=S1.lower_bound(pii({s, 2e9}));
			if(it==S1.end()) return false;
			if(jt==S1.begin()) return false;
			jt--;
			if(Find(it->first)!=u) return false;
			if(Find(jt->first)!=u) return false;
			if(Find(it->second)==Find(jt->second)) return true;
			else return false;
		}
	}
}

int chk[MAXM+10];

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++)
	{
		scanf(" %c%d%d", &A[i].c, &A[i].x, &A[i].y);
		if(A[i].x<=N) comp1.push_back(A[i].x);
		else comp2.push_back(A[i].x);
		if(A[i].y<=N) comp1.push_back(A[i].y);
		else comp2.push_back(A[i].y);
		if(A[i].c!='Q' && A[i].x>A[i].y) swap(A[i].x, A[i].y);
	}

	sort(comp1.begin(), comp1.end());
	comp1.erase(unique(comp1.begin(), comp1.end()), comp1.end());

	sort(comp2.begin(), comp2.end());
	comp2.erase(unique(comp2.begin(), comp2.end()), comp2.end());

	N1=comp1.size();
	N2=comp2.size();

	for(int i=1; i<=M; i++)
	{
		if(A[i].x<=N) A[i].x=lower_bound(comp1.begin(), comp1.end(), A[i].x)-comp1.begin()+1;
		else A[i].x=lower_bound(comp2.begin(), comp2.end(), A[i].x)-comp2.begin()+1+N1;

		if(A[i].y<=N) A[i].y=lower_bound(comp1.begin(), comp1.end(), A[i].y)-comp1.begin()+1;
		else A[i].y=lower_bound(comp2.begin(), comp2.end(), A[i].y)-comp2.begin()+1+N1;
	}

	init();
	for(int i=1; i<=M; i++)
	{
		if(A[i].c=='B')
		{
			chk[A[i].x]++;
		}
		if(A[i].c=='A')
		{
			S[A[i].x].insert({A[i].y, A[i].x});
			S[A[i].y].insert({A[i].x, A[i].y});

			S1.insert({A[i].y, A[i].x});
			S2.insert({A[i].x, A[i].y});
		}
	}

	for(int i=1; i<=N1+N2; i++)
	{
		if(i==N1) continue;
		if(i==N1+N2) continue;
		if(chk[i]) continue;
		Union(i, i+1);
	}

	vector<int> ans;
	for(int i=M; i>=1; i--)
	{
		//printf("DONE %d\n", i);
		if(A[i].c=='A')
		{
			assert(A[i].x<=N1);
			assert(A[i].y>N1);
			S[Find(A[i].x)].erase({A[i].y, A[i].x});
			S[Find(A[i].y)].erase({A[i].x, A[i].y});

			S1.erase({A[i].y, A[i].x});
			S2.erase({A[i].x, A[i].y});
		}
		if(A[i].c=='B')
		{
			assert(A[i].x+1==A[i].y);
			Union(A[i].x, A[i].y);
		}
		if(A[i].c=='Q')
		{
			if(solve(A[i].x, A[i].y)) ans.push_back(1);
			else ans.push_back(0);
		}
	}

	reverse(ans.begin(), ans.end());
	for(auto it : ans)
	{
		if(it) printf("DA\n");
		else printf("NE\n");
	}
}

Compilation message (stderr)

mostovi.cpp: In function 'bool solve(int, int)':
mostovi.cpp:65:7: warning: variable 'l1' set but not used [-Wunused-but-set-variable]
   65 |   int l1, r1, l2, r2;
      |       ^~
mostovi.cpp:65:15: warning: variable 'l2' set but not used [-Wunused-but-set-variable]
   65 |   int l1, r1, l2, r2;
      |               ^~
mostovi.cpp:80:11: warning: variable 'r1' set but not used [-Wunused-but-set-variable]
   80 |   int l1, r1, l2, r2;
      |           ^~
mostovi.cpp:80:19: warning: variable 'r2' set but not used [-Wunused-but-set-variable]
   80 |   int l1, r1, l2, r2;
      |                   ^~
mostovi.cpp:137:1: warning: control reaches end of non-void function [-Wreturn-type]
  137 | }
      | ^
mostovi.cpp: In function 'int main()':
mostovi.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  143 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
mostovi.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  146 |   scanf(" %c%d%d", &A[i].c, &A[i].x, &A[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100