QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#109449 | #5201. Cactus Meets Torus | gigabuffoon | Compile Error | / | / | C++20 | 4.7kb | 2023-05-29 02:15:07 | 2023-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]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [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); | ^