Submission #353740

#	Time	Username	Problem	Language	Result	Execution time	Memory
353740		arnold518	Mostovi (COI14_mostovi)	C++14	60 / 100	1096 ms	19864 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 chk[MAXM+10], bridge[MAXM+10];

bool vis[MAXM+10];
void dfs(int now)
{
	vis[now]=true;
	if(now<N1)
	{
		if(!chk[now] && !vis[now+1]) dfs(now+1);
	}
	if(N1+1<now)
	{
		if(!chk[now] && !vis[now-1]) dfs(now-1);
	}
	if(bridge[now]!=0)
	{
		if(!vis[bridge[now]]) dfs(bridge[now]);
	}
}

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);
	}
	comp1.push_back(N);
	comp2.push_back(N+1);

	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();
	//N1=N;
	//N2=N;

	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;
	}
	for(int i=1; i<=M; i++)
	{
		if(A[i].c=='A')
		{
			bridge[A[i].x]=A[i].y;
			bridge[A[i].y]=A[i].x;
		}
		if(A[i].c=='B')
		{
			if(A[i].x<=N1) chk[A[i].x]=1;
			else chk[A[i].y]=1;
		}
		if(A[i].c=='Q')
		{
			for(int i=1; i<=N1+N2; i++) vis[i]=0;
			dfs(A[i].x);
			if(vis[A[i].y]) printf("DA\n");
			else printf("NE\n");
		}
	}
	return 0;
}

Compilation message (stderr)

mostovi.cpp: In function 'int main()':
mostovi.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
mostovi.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |   scanf(" %c%d%d", &A[i].c, &A[i].x, &A[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100