QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#304370 | #5201. Cactus Meets Torus | LaStataleBlue | WA | 25ms | 11948kb | C++23 | 3.4kb | 2024-01-13 18:38:10 | 2024-01-13 18:38:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
vector<vector<int>> grafo;
vector<pair<int,int>> edges;
vi num, st; vector<vector<pii>> ed; int Time;
template<class F> int dfs(int at, int par, F& f) {
int me = num[at] = ++Time, e, y, top = me;
for (auto pa : ed[at]) if (pa.second != par) {
tie(y, e) = pa;
if (num[y]) {
top = min(top, num[y]);
if (num[y] < me)
st.push_back(e);
} else {
int si = sz(st); int up = dfs(y, e, f);
top = min(top, up);
if (up == me) {
st.push_back(e);
f(vi(st.begin() + si, st.end()));
st.resize(si);
}
else if (up < me) st.push_back(e);
else{
grafo[edges[e].first].push_back(edges[e].second);
grafo[edges[e].second].push_back(edges[e].first);
}
}
}
return top;//idea per block cut tree: collego ogni
} //nodo con un nodo che rappresenta la sua bicomp.
template<class F> void bicomps(F f) { //0-based
num.assign(sz(ed), 0);
rep(i,0,sz(ed)) if (!num[i]) dfs(i, -1, f);
}
void solve(){
int n,m;
cin>>n>>m;
if(n==0 && m==0)exit(0);
grafo = vector(n,vector<int>());
edges.clear();
ed.clear();
num.clear();st.clear();Time=0;
int eid = 0;
ed.resize(n);
for(int i=0;i<m;i++){
int s;
cin>>s;
int u;
cin>>u;
u--;
for(int j=0;j<s-1;j++){
int v;
cin>>v;
v--;
edges.push_back({u,v});
ed[u].emplace_back(v,eid);
ed[v].emplace_back(u,eid++);
u=v;
}
}
int cc = 0;
bicomps([&](const vi& edgelist){
grafo.push_back(vector<int>());
unordered_set<int> ds;
for(auto i : edgelist){
auto [u,v] = edges[i];
ds.insert(u);
ds.insert(v);
}
for(auto i : ds){
grafo[n+cc].push_back(i);
grafo[i].push_back(n+cc);
}
cc++;
});
if(cc<=1){
cout<<"Yes\n";
}else{
vector grafo2(n+cc,vector<int>());
auto dfs = [&](auto &dfs,int nodo,int last)->bool{
bool res=(nodo>=n);
for(auto i : grafo[nodo]){
if(i!=last){
if(dfs(dfs,i,nodo)){
res=true;
grafo2[nodo].push_back(i);
grafo2[i].push_back(nodo);
}
}
}
return res;
};
dfs(dfs,n,-1);
for(int i=0;i<n+cc;i++){
int cont=0;
for(auto j : grafo2[i]){
if(grafo2[j].size()!=1)cont++;
}
if(cont>2){
cout<<"No\n";
return;
}
}
cout<<"Yes\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
//cin>>t;
while(true)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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: 0
Accepted
time: 0ms
memory: 3640kb
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:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes
result:
ok 18 token(s): yes count is 18, no count is 0
Test #3:
score: 0
Accepted
time: 20ms
memory: 3568kb
input:
6 1 8 6 1 2 3 1 4 5 1 6 1 8 5 1 2 3 1 4 6 1 6 1 8 4 1 2 3 1 5 6 1 6 2 6 4 1 2 3 1 5 2 1 6 6 1 8 6 1 2 4 1 3 5 1 6 1 8 5 1 2 4 1 3 6 1 6 1 8 3 1 2 4 1 5 6 1 6 2 6 3 1 2 4 1 5 2 1 6 6 1 8 6 1 2 5 1 3 4 1 6 1 8 4 1 2 5 1 3 6 1 6 1 8 3 1 2 5 1 4 6 1 6 2 6 3 1 2 5 1 4 2 1 6 6 1 8 5 1 2 6 1 3 4 1 6 1 8 4 ...
output:
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 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 ...
result:
ok 15304 token(s): yes count is 15304, no count is 0
Test #4:
score: 0
Accepted
time: 20ms
memory: 3812kb
input:
7 2 6 6 4 1 3 2 7 3 3 5 4 7 2 6 6 5 3 1 4 5 3 3 2 7 7 1 8 5 3 1 4 6 7 2 3 7 2 7 4 1 3 2 7 5 3 2 6 7 7 2 6 4 1 3 2 7 6 2 3 5 7 1 9 5 7 2 3 1 4 6 3 7 7 2 7 5 4 1 3 2 7 4 2 3 6 7 2 6 4 1 3 2 7 5 2 3 6 7 2 6 1 3 2 7 4 1 4 4 5 6 4 7 1 8 5 4 1 3 2 7 4 6 7 1 8 7 2 3 1 4 5 6 4 7 2 7 5 4 1 3 2 7 4 2 6 7 7 1 ...
output:
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 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 ...
result:
ok 14334 token(s): yes count is 14334, no count is 0
Test #5:
score: 0
Accepted
time: 21ms
memory: 3576kb
input:
8 1 11 2 1 3 6 1 4 7 1 5 8 1 8 3 3 2 1 3 6 6 1 4 5 1 7 2 1 8 8 3 5 8 2 1 3 2 4 4 1 5 4 4 1 6 7 1 8 1 10 6 1 2 3 1 4 5 1 7 8 8 2 6 3 1 2 4 1 5 4 6 1 7 8 8 2 9 3 1 2 7 1 4 6 1 5 2 7 8 8 2 4 5 1 2 8 7 3 1 4 7 1 6 3 8 1 10 2 1 3 5 1 4 8 7 1 6 8 2 9 2 1 3 6 1 4 7 1 5 2 7 8 8 2 9 2 1 3 7 1 4 6 1 5 2 3 8 8...
output:
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 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 ...
result:
ok 12577 token(s): yes count is 12577, no count is 0
Test #6:
score: 0
Accepted
time: 21ms
memory: 3576kb
input:
8 3 6 5 1 3 4 2 6 2 1 7 2 3 8 8 2 9 5 1 3 4 2 6 4 7 1 2 6 8 8 2 8 4 2 6 3 1 5 3 8 2 1 7 8 2 5 7 1 3 5 1 6 5 4 2 6 8 4 8 2 8 7 1 3 6 2 4 5 1 2 3 8 8 2 8 4 2 6 3 1 5 7 1 3 3 8 6 8 2 6 4 2 6 3 1 5 4 1 7 8 3 8 1 10 8 7 1 3 6 2 4 6 5 1 8 2 5 5 1 3 7 1 6 2 4 8 7 6 2 8 2 4 5 1 3 8 6 1 7 4 2 6 4 8 2 9 3 1 5...
output:
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 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 ...
result:
ok 12574 token(s): yes count is 12574, no count is 0
Test #7:
score: 0
Accepted
time: 15ms
memory: 3632kb
input:
8 2 5 2 3 6 8 4 4 7 1 5 8 8 2 5 2 3 7 1 5 5 3 8 6 7 4 8 2 6 2 3 7 1 5 8 4 4 6 7 4 8 1 10 2 3 7 1 5 7 4 8 6 7 8 1 9 2 3 7 1 5 7 4 8 6 8 2 8 2 3 8 5 1 7 4 6 2 7 8 8 2 8 2 3 8 4 6 7 1 5 2 6 8 8 2 7 2 3 8 4 7 1 5 3 7 6 8 8 2 4 2 3 8 4 6 6 8 7 1 5 7 8 1 10 8 3 5 1 7 2 4 6 2 5 8 2 7 3 8 7 1 5 2 4 3 6 2 7 ...
output:
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 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 ...
result:
ok 9303 token(s): yes count is 9303, no count is 0
Test #8:
score: -100
Wrong Answer
time: 25ms
memory: 11948kb
input:
12 2 14 4 7 3 9 1 2 9 7 8 10 5 6 10 7 3 6 11 12 12 2 14 4 3 1 9 11 3 5 7 6 10 2 12 10 7 3 3 8 5 12 3 11 2 1 5 3 6 4 11 6 7 10 6 4 1 9 8 2 3 3 12 5 12 3 6 3 1 9 2 4 11 5 1 10 2 12 4 7 6 5 7 9 5 8 6 12 2 12 5 1 3 8 4 2 6 4 7 8 9 3 5 1 11 10 12 11 12 4 9 9 1 2 4 3 5 4 11 1 2 4 12 4 2 7 10 2 4 5 6 8 5 1...
output:
Yes Yes Yes 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 No No No No No No No No No No No
result:
wrong answer expected YES, found NO [13th token]