QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#109449#5201. Cactus Meets TorusgigabuffoonCompile Error//C++204.7kb2023-05-29 02:15:072023-05-29 02:15:15

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-29 02:15:15]
  • 评测
  • [2023-05-29 02:15:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define all(a) begin(a),end(a)
#define sz(a) int(size(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
using vi = vector<int>;
using ll = long long int;
using pii = pair<int, int>;

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 {
                // bridge
                st.push_back(e);
                f(vi(st.begin() + si, st.end()));
                st.resize(si);
            }
        }
    }
    return top;
}

template<class F>
void twoVCCs(F f){
    num.assign(sz(ed), 0);
    rep(i,0,sz(ed)) if(!num[i]) dfs(i, -1, f);
}

vector<vector<pii>> trimLeaves(vector<vector<pii>> ed, vector<bool> protect){
    int n = sz(ed);
    vector<bool> dead(n);
    vector<int> deg(n);

    for(int u = 0; u < n; ++u){
        for(auto [v, id] : ed[u]){
            ++deg[u];
            ++deg[v];
        }
    }

    queue<int> q;
    for(int i = 0; i < n; ++i){
        if(deg[i] <= 1){
            q.push(i);
        }
    }

    while(sz(q)){
        int curr = q.front();
        q.pop();

        if(protect[curr]) continue;
        dead[curr] = true;
        for(auto [to, eid] : ed[curr]) {
            if(!dead[to]) {
                --deg[curr], --deg[to];
                if(deg[to] == 1)
                    q.push(to);
            }
        }
        // remove this guy?
    }

    vector<vector<pii>> res(n);
    rep(i,0,n) if(!dead[i])
        for(auto [v, eid] : ed[i])
            if(!dead[v])
                res[u].emplace_back(v, eid);
    // do some stuff
    return res;
}

bool solve(int tc) {
    int n, m;
    cin >> n >> m;

    if(n == 0 && m == 0) return false;

    ed = vector<vector<pii>>(n);
    vector<pii> initEdgeList;
    int eID = 0;
    for(int i = 0; i < m; ++i){
        int num;
        cin >> num;

        int prev;
        cin >> prev;
        --prev;
        for(int it = 1; it < num; ++it){
            int curr;
            cin >> curr;
            --curr;

            initEdgeList.emplace_back(prev, curr);
            ed[prev].emplace_back(curr, eID);
            ed[curr].emplace_back(prev, eID++);
        }
    }

    vector<bool> protect(n);
    ed = trimLeaves(ed, protect);
    n = sz(ed);
    if(n <= 1){
        cout << "YES\n";
        return true;
    }

    // do lowlink
    int metaN = n;
    vector<vector<pii>> metaAdj(n);
    twoVCCs([&](vector<int> list){
        for(int eid : list){
            auto [u, v] = initEdgeList[eid];
            metaAdj[u].emplace_back(metaN, -1);
            metaAdj[v].emplace_back(metaN, -1);
        }
        metaAdj.push_back({});
        ++metaN;
    });

    for(int u = 0; u < n; ++u){
        sort(all(metaAdj[u]));
        metaAdj[u].erase(unique(all(metaAdj[u])), end(metaAdj[u]));

        for(auto [v, eid] : metaAdj[u]){
            metaAdj[v].emplace_back(u, -1);
        }
    }

    for(int u = 0; u < metaN; ++u){
        sort(all(metaAdj[u]));
        metaAdj[u].erase(unique(all(metaAdj[u])), end(metaAdj[u]));
    }

    protect = vector<bool>(metaN);
    for(int u = 0; u < n; ++u){
        if(sz(metaAdj[u]) > 1) protect[u] = true;
    }

    metaAdj = trimLeaves(metaAdj, protect);
    metaN = sz(metaAdj);

    vector<int> deg(metaN);
    for(int u = 0; u < metaN; ++u){
        for(auto [v, eid] : metaAdj[u]){
            ++deg[u];
            ++deg[v];
        }
    }

    for(int u = 0; u < metaN; ++u){
        for(auto [v, eid] : metaAdj[u]){
            cout << u << " " << v << endl;
        }
    }

    int maxDeg = 0;
    for(int i = 0; i < n; ++i){
        maxDeg = max(maxDeg, deg[i]);
    }

    if(maxDeg >= 3){
        cout << "NO\n";
    }
    else{
        cout << "YES\n";
    }

    return true;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int t = 1;
    // cin >> t;
    // for(int i = 1; i <= t; i++) solve(i);

    while(solve(t));

    cout.flush(); return 0;
}
/*

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

*/

詳細信息

answer.code: In function ‘std::vector<std::vector<std::pair<int, int> > > trimLeaves(std::vector<std::vector<std::pair<int, int> > >, std::vector<bool>)’:
answer.code:88:21: error: ‘u’ was not declared in this scope
   88 |                 res[u].emplace_back(v, eid);
      |                     ^