oj.uz

답안 #353734

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
353734 2021-01-21T09:50:08 Z arnold518 Mostovi (COI14_mostovi) C++14
10 / 100
 1000 ms 20232 KB 
#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<=N) 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

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
10.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 3 ms 364 KB Output isn't correct
3 Incorrect 2 ms 364 KB Output isn't correct
4 Incorrect 2 ms 364 KB Output isn't correct
5 Correct 13 ms 492 KB Output is correct
6 Incorrect 2 ms 364 KB Output isn't correct
7 Execution timed out 1084 ms 13284 KB Time limit exceeded
8 Execution timed out 1055 ms 20232 KB Time limit exceeded
9 Execution timed out 1032 ms 12632 KB Time limit exceeded
10 Execution timed out 1096 ms 10660 KB Time limit exceeded