QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373779 | #5201. Cactus Meets Torus | InfinityNS | WA | 1ms | 6156kb | C++14 | 2.6kb | 2024-04-02 05:38:13 | 2024-04-02 05:38:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
vector<int> E[N];
void AddEdge(int u,int v){
E[u].pb(v);
E[v].pb(u);
}
int par[N];
bool was[N];
vector<int> cycLca;
vector<pair<int,int>> cyc;
int cnt[N];
int lid[N],rid[N],tid;
void DFS(int u,int p){
par[u]=p;
was[u]=true;
lid[u]=++tid;
for(int v:E[u]){
if(v!=p){
if(was[v]){
if(lid[v]<lid[u]){
cycLca.pb(v);
cyc.pb({u,v});
for(int i=u;i!=par[v];i=par[i]){
cnt[i]++;
}
}
}else{
DFS(v,u);
}
}
}
rid[u]=tid;
}
bool In(int a,int b){
return lid[a]<=lid[b] && rid[a]>=lid[b];
}
int main(){
while(true){
int n,m;
scanf("%i %i",&n,&m);
if(n==0)break;
for(int i=1;i<=m;i++){
int sz;
scanf("%i",&sz);
vector<int> nodes(sz,0);
for(int&j:nodes)scanf("%i",&j);
for(int j=1;j<nodes.size();j++){
AddEdge(nodes[j-1],nodes[j]);
}
}
cycLca.clear();
DFS(1,0);
sort(cycLca.begin(),cycLca.end(),[&](int i,int j){return lid[i]<lid[j];});
int lastCycNode=cycLca.size()?cycLca.back():0;
for(int i=1;i<=n;i++){
was[i]=false;
par[i]=0;
cnt[i]=0;
}
//printf("lastCycNode %i\n",lastCycNode);
if(!lastCycNode){
printf("Yes\n");
}else{
cycLca.clear();
cyc.clear();
DFS(lastCycNode,0);
//printf("lastCycNode %i\n",lastCycNode);
bool ok=true;
sort(cycLca.begin(),cycLca.end(),[&](int i,int j){return lid[i]<lid[j];});
int fir=cycLca.front();
int las=cycLca.back();
//for(int lca:cycLca)printf("cycLca %i (%i %i)\n",lca,lid[lca],rid[lca]);
for(int i=1;i<cycLca.size();i++){
//printf("cycLca %i\n",lca);
if(rid[cycLca[i-1]]<lid[cycLca[i]]){
ok=false;
}
}
if(ok){
ok=false;
bool good=true;
for(auto p:cyc){
int deg=0,sec=0;
for(int i=p.first;i!=par[p.second];i=par[i]){
deg+=cnt[i]-1;
if(cnt[i]>1)sec++;
}
if(deg==cyc.size()-1)ok=true;
//if(sec>2 || (sec>1 && cnt[par[p.second]]==0 && par[p.second]!=0))good=false;
//if(sec>1 && (p.second==fir || p.second==las))good=false;
}
sort(cyc.begin(),cyc.end(),[&](pair<int,int> a,pair<int,int> b){return lid[a.second]<lid[b.second];});
for(int i=2;i<cyc.size();i++){
if(In(cyc[i-2].second,cyc[i].second) && In(cyc[i].second,cyc[i-2].first))good=false;
}
if(ok || good)printf("Yes\n");
else printf("No\n");
}else{
printf("No\n");
}
}
for(int i=1;i<=n;i++){
was[i]=false;
par[i]=0;
E[i].clear();
cnt[i]=0;
}
tid=0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6156kb
input:
6 1 8 1 2 3 1 4 5 6 4 10 2 9 1 2 3 1 10 4 5 6 4 5 7 8 9 7 10 0 0
output:
Yes No
result:
ok 2 token(s): yes count is 1, no count is 1
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 6112kb
input:
15 3 9 1 2 3 4 5 6 7 8 3 7 2 9 10 11 12 13 10 5 2 14 9 15 10 15 7 3 1 2 3 3 4 2 5 3 6 2 7 3 8 2 9 3 10 2 11 3 12 2 13 3 14 2 15 1 0 2 1 2 1 2 2 1 2 2 1 3 1 4 1 3 2 1 4 2 3 1 2 3 2 2 4 6 2 5 1 2 3 4 5 2 4 6 7 3 5 1 2 3 4 5 2 4 6 2 4 7 7 2 6 1 2 3 4 5 6 2 5 7 8 3 6 1 2 3 4 5 6 2 5 7 2 5 8 9 4 5 1 2 3 ...
output:
No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes
result:
wrong answer expected YES, found NO [1st token]