QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#304370#5201. Cactus Meets TorusLaStataleBlueWA 25ms11948kbC++233.4kb2024-01-13 18:38:102024-01-13 18:38:11

Judging History

你现在查看的是最新测评结果

  • [2024-01-13 18:38:11]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:11948kb
  • [2024-01-13 18:38:10]
  • 提交

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;
}

详细

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]