#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
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
13 ms |
492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
364 KB |
Output is correct |
| 7 |
Execution timed out |
1086 ms |
13400 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1096 ms |
19864 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1086 ms |
12592 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1093 ms |
10624 KB |
Time limit exceeded |
