QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #460423 | #2679. 校园旅行 | Lynkcat | 100 ✓ | 486ms | 37304kb | C++14 | 2.7kb | 2024-07-01 16:05:59 | 2024-07-01 16:05:59 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
// #define int ll
// #define N
using namespace std;
const int N=5005;
int vis[N],ffa[N];
poly G[N],E[N];
bool a[N],dp[N][N];
int n,m,q;
poly g;
int bl;
void dfs(int k,int fa)
{
g.push_back(k);
ffa[k]=fa;
for (auto u:G[k])
if (a[u]==a[k])
{
if (!vis[u]) vis[u]=3-vis[k],dfs(u,k);
else
{
if (vis[u]!=3-vis[k]) bl=1;
}
}
}
void dfs1(int k,int fa)
{
g.push_back(k);
ffa[k]=fa;
for (auto u:G[k])
if (a[u]!=a[k])
{
if (!vis[u]) vis[u]=3-vis[k],dfs1(u,k);
else
{
if (vis[u]!=3-vis[k]) bl=1;
}
}
}
void BellaKira()
{
cin>>n>>m>>q;
for (int i=1;i<=n;i++)
{
char c;
cin>>c;
a[i]=c-'0';
}
for (int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int i=1;i<=n;i++)
if (!vis[i])
{
poly().swap(g);
bl=0;
vis[i]=1;
dfs(i,0);
for (auto u:g)
if (ffa[u]) E[ffa[u]].push_back(u),E[u].push_back(ffa[u]);
if (bl) E[i].push_back(i);
}
for (int i=1;i<=n;i++) vis[i]=0;
for (int i=1;i<=n;i++)
if (!vis[i])
{
poly().swap(g);
bl=0;
vis[i]=1;
dfs1(i,0);
// for (auto u:g) cout<<u<<",";
// cout<<endl;
for (auto u:g)
if (ffa[u]) E[ffa[u]].push_back(u),E[u].push_back(ffa[u]);
if (bl) E[i].push_back(i);
}
{
queue<pa>q;
for (int i=1;i<=n;i++)
dp[i][i]=1,q.push(mp(i,i));
for (int i=1;i<=n;i++)
for (auto u:E[i])
if (a[i]==a[u]&&!dp[i][u]) dp[i][u]=1,q.push(mp(i,u));
while (!q.empty())
{
auto [x,y]=q.front();q.pop();
// cout<<x<<" "<<y<<endl;
for (int i:E[x])
for (int j:E[y])
if (a[i]==a[j]&&!dp[i][j])
dp[i][j]=1,q.push(mp(i,j));
}
}
while (q--)
{
int x,y;
cin>>x>>y;
if (dp[x][y]) cout<<"YES\n";
else cout<<"NO\n";
}
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
詳細信息
Test #1:
score: 10
Accepted
time: 335ms
memory: 37304kb
input:
3000 10000 100000 110000100010110011101010100100001001000101110111011011101111111001100001011010101011001010100001011111001010100011101100101111110001011100000011000010101101010110110111001011110100100011000110101011000110110000011010101100000101111011010001110010011100010111110100010000011001001101...
output:
YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES...
result:
ok 100000 lines
Test #2:
score: 10
Accepted
time: 159ms
memory: 20228kb
input:
3000 9265 100000 0111101100111000110010101001111100011111111011000111101101010000011110010100011011000011100001111011010001010110100011001111011010101111011101101101111010001110101010000000111110011000101110111011001101000010111101011011000110101010001110011111101100111011010001101110011000001010001...
output:
NO YES YES YES NO YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES NO NO YES YES YES YES YES YES NO YES NO YES YES YES YES YES YES YES NO NO YES YES YES YES YES NO YES YES NO YES YES YES NO YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES NO YES NO YES YES YES NO YES YES NO Y...
result:
ok 100000 lines
Test #3:
score: 10
Accepted
time: 146ms
memory: 20036kb
input:
3000 10000 100000 111101111111010000110001010110001111111011000110100101100000111110000110011010010001100110110011100010011100011001000111110100101011010001100010011010100001011101001000110000110111000100111010010001111111011100111000011110110111011111100111100101011110011111111001100011100100111111...
output:
NO YES YES YES YES YES YES YES NO YES NO NO YES NO YES YES NO YES YES YES YES NO NO YES NO YES YES YES YES NO NO NO YES NO YES YES NO YES YES YES NO YES YES YES YES NO NO YES YES YES NO YES YES YES YES YES NO NO NO YES YES YES NO YES NO YES NO YES NO YES NO NO NO YES YES YES NO NO YES NO YES YES YES...
result:
ok 100000 lines
Test #4:
score: 10
Accepted
time: 74ms
memory: 20984kb
input:
3000 50000 100000 010100100001111000100101000001011111100010100010101010100110100010110010110000011010100001001110000101100000001101100010001001011001110010101011011011011000101111111100011010000001110100001001010111011111011001100011111000011000011101001100010111000111010001100010100111110010001011...
output:
NO NO NO NO NO YES YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO YES NO NO NO NO YES NO NO YES YES NO NO YES NO NO NO NO NO NO NO ...
result:
ok 100000 lines
Test #5:
score: 10
Accepted
time: 119ms
memory: 19740kb
input:
3000 50000 100000 001000000001001110011111011010101001000101110110000110011100101010010011101000110010111010001010110001011000111100111101100000111000101111011010000101101111110010000111011100100001111000000001111110000110100011100010110111100101000110111011000001111100000111101000001101001110101010...
output:
YES YES NO NO NO YES YES YES YES NO NO NO YES NO NO NO NO NO NO YES YES YES YES NO NO YES NO NO YES NO NO NO YES YES NO YES YES YES NO NO NO YES YES NO YES NO NO NO YES YES NO YES YES YES NO YES YES YES NO YES YES YES YES YES NO NO YES NO YES YES YES YES NO YES NO YES YES YES YES YES NO NO YES YES N...
result:
ok 100000 lines
Test #6:
score: 10
Accepted
time: 143ms
memory: 20636kb
input:
3000 50000 100000 110011011010100101101101100111100110011110101011111001101011110110101010101110000111111001000001100011100011001100010011011101101011010000100101000110110111001111111001111011001110101110001110110100010000111100000101101111000001111010011101100111111110010001011011101001011110100111...
output:
YES YES YES YES NO YES YES NO YES YES YES YES YES NO YES YES YES YES NO YES NO YES NO YES YES NO NO NO NO YES NO YES NO YES NO YES NO YES NO NO NO YES YES NO YES YES NO NO YES NO YES NO YES YES YES NO YES YES YES NO NO YES YES NO YES NO YES YES NO NO NO NO NO NO YES NO YES NO YES YES NO YES YES YES ...
result:
ok 100000 lines
Test #7:
score: 10
Accepted
time: 165ms
memory: 21024kb
input:
3000 50000 100000 111011101011110010111011011110110011101010100000101111100100011001000010110001010000101111010110110000110111100011110101000100001100100100011011100010010010101111100010000010011101001101000001111011001011101001101111100001100001101100100110011010001101111101100111001010111100100011...
output:
NO YES YES YES NO YES NO YES NO YES YES NO YES YES NO YES NO YES YES YES NO YES YES YES YES YES NO NO NO NO YES YES YES YES YES YES NO NO YES YES YES YES YES YES NO NO YES YES YES NO YES YES YES NO YES YES YES YES NO YES YES YES NO YES NO YES NO YES NO YES YES YES YES YES YES YES YES YES YES YES YES...
result:
ok 100000 lines
Test #8:
score: 10
Accepted
time: 479ms
memory: 33544kb
input:
5000 361135 100000 00000011101011100011110101101001100110010001101001100101101001111010101110111010111100110000010110011100100100011100101010011011000011111010110111011010100001010011001110001111010001110010000000100110101111000110111001111011110111100000110011101101000110001111001101000111010011111...
output:
YES NO NO YES NO YES YES YES YES NO YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES NO YES YES YES YES YES NO NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES NO YES ...
result:
ok 100000 lines
Test #9:
score: 10
Accepted
time: 486ms
memory: 35360kb
input:
5000 500000 100000 10101100011011001010110100000010100001110111001010100100100100000010010001001011001110001010110000000010110011010101010101001011110111001001100001001011011001001010110101111001101111110010001101010010101001101100110100001010000110001100011001001110110110100100100101111101000001111...
output:
NO NO NO YES NO YES NO YES YES YES YES NO YES YES YES YES NO NO YES YES YES YES YES NO YES NO YES YES NO YES YES NO YES NO YES YES YES NO NO YES YES NO YES NO NO YES YES YES YES NO NO NO NO NO YES NO YES NO NO NO YES YES YES YES YES YES YES NO NO YES YES NO YES YES NO NO YES NO YES NO NO YES NO NO Y...
result:
ok 100000 lines
Test #10:
score: 10
Accepted
time: 476ms
memory: 35396kb
input:
5000 500000 100000 11011101110101000011000010101011101000000011001111101011111001010111000101110000011100100101011001011011011001011111011101000111010101100000000110001010011000010101010100000101101001100101010001111011001100111001001001011000001000100111011110101011011100010011100001101000001010110...
output:
NO YES YES YES NO NO NO YES YES NO NO NO NO YES YES NO YES YES YES YES NO YES YES YES YES YES NO YES YES NO YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES NO NO YES YES YES YES YES YES YES YES YES YES NO YES NO YES YES NO NO YES NO NO YES YES YES YES YES NO...
result:
ok 100000 lines