Submission #2246569
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
template<class Data> struct Graph;
struct DefData {
struct VData {};
struct GData {};
using Len = int;
struct EData {
Len len;
EData() : len(1) {}
};
static const Len INF = 0x33433433;
};
template<class Data=DefData>
struct Graph {
using VData = typename Data::VData;
using EData = typename Data::EData;
using GData = typename Data::GData;
struct Edge {
int to;
int rev_idx;
bool is_es;
EData dat;
};
using Len = typename remove_const<decltype(Data::INF)>::type;
using Ls = vector<Len>;
using Es = vector<Edge>;
Len INF = Data::INF;
int n;
GData gdat;
vector<VData> vdat;
vector<Es> es;
vector<Es> res;
vector<Ls> cost;
Graph() {}
Graph(int sz) {
Init(sz);
}
void Init(int sz) {
n = sz;
vdat.resize(sz);
es.resize(sz);
res.resize(sz);
}
void AddEdge(int u, int v, EData d, EData r) {
es[u].emplace_back(Edge{v, 0, true, d});
res[v].emplace_back(Edge{u, 0, false, r});
es[u].back().rev_idx = res[v].size()-1;
res[v].back().rev_idx = es[u].size()-1;
}
void AddEdge(int u, int v, EData d=EData()) {
AddEdge(u, v, d, d);
}
void AddEdgeForFlow(int u, int v, EData d) {
AddEdge(u, v, d, EData());
}
Edge *GetRevEdge(Edge *e) {
int v = e->to;
if (e->is_es) return &res[v][e->rev_idx];
return &es[v][e->rev_idx];
}
// should be tested
template<class Cmp>
void EraseMultipleEdge(Cmp cmp, bool really_erase) {
auto same = [](const Edge &a, const Edge &b) {
return a.to == b.to;
};
vector<Es> new_res(n);
for (int v=0; v<n; v++) {
auto &ves = es[v];
sort(ves.begin(), ves.end(), cmp);
auto itr = unique(ves.begin(), ves.end(), same);
if (really_erase) ves.erase(itr, ves.end());
for (int i=0; i<ves.size(); i++) {
auto &e = ves[i];
int u = e.to;
new_res[u].emplace_back(Edge{v, i, false, GetRevEdge(&e)->dat});
}
}
res.swap(new_res);
}
void CreateAdjMat() {
cost.clear();
cost.resize(n, Ls(n, INF));
auto cmp = [](const Edge &a, const Edge &b) {
if (a.to != b.to) return a.to < b.to;
return a.dat.len < b.dat.len;
};
EraseMultipleEdge(cmp, false);
for (int i=0; i<n; i++) {
int prev = -1;
for (auto &e : es[i]) {
int v = e.to;
if (prev > v) break;
cost[i][v] = min(cost[i][v], e.dat.len);
prev = v;
}
}
}
void DijkstraV(vector<int> &starts, Ls &d) {
d.clear();
d.resize(n, INF);
for (int s : starts) d[s] = 0;
if (cost.empty()) CreateAdjMat();
vector<bool> used(n, false);
for (int i=0; i<n; i++) {
int v = -1;
for (int u=0; u<n; u++) {
if (used[u]) continue;
if (v == -1 || d[u] < d[v]) {
v = u;
}
}
if (v == -1) return;
used[v] = true;
for (int u=0; u<n; u++) {
d[u] = mind(d[u], d[v] + cost[v][u]);
}
}
// must not reach here
assert(0);
}
void DijkstraE(vector<int> &starts, Ls &d) {
using Pair = pair<Len, int>;
priority_queue<Pair, vector<Pair>, greater<Pair> > q;
d.clear();
d.resize(n, INF);
for (int s : starts) {
d[s] = 0;
q.push(Pair(0, s));
}
while (!q.empty()) {
Pair p = q.top(); q.pop();
int v = p.second;
if (d[v] < p.first) continue;
for (auto &e : es[v]) {
int u = e.to;
Len nd = d[v] + e.dat.len;
if (d[u] > nd) {
d[u] = nd;
q.push(Pair(nd, u));
}
}
}
}
// return true if a graph has a negative cycle in the reachnable scope from starts
bool SPFA(vector<int> &starts, Ls &d) {
d.clear();
d.resize(n, INF);
if (n == 1) {
d[0] = 0;
return false;
}
queue<int> q;
vector<bool> inq(n);
vector<int> cnt(n);
for (int s : starts) {
inq[s] = true;
q.push(s);
d[s] = 0;
}
while (!q.empty()) {
int v = q.front(); q.pop();
inq[v] = false;
cnt[v]++;
if (cnt[v] > n) continue;
for (auto &e : es[v]) {
int u = e.to;
Len nd = d[v] + e.dat.len;
if (d[u] > nd) {
d[u] = nd;
if (inq[u]) continue;
inq[u] = true;
q.push(u);
}
}
}
// do DFS if you need the concrete contents of such cycles
for (int i=0; i<n; i++) {
if (cnt[i] >= n) return true;
}
return false;
}
void DijkstraV(int s, Ls &d) {
vector<int> ss(1, s);
DijkstraV(ss, d);
}
void DijkstraE(int s, Ls &d) {
vector<int> ss(1, s);
DijkstraE(ss, d);
}
// return true if the graph has a negative cycle
bool SPFA(int s, Ls &d) {
vector<int> ss(1, s);
return SPFA(ss, d);
}
// Create "Shortest Path Graph", which should be DAG
Graph<Data> RestoreShortestPaths(Ls &d) {
Graph<Data> ret(n);
for (int i=0; i<n; i++) {
for (auto &e : es[i]) {
int v = e.to;
if (d[v] == d[i] + e.dat.len) {
ret.AddEdge(i, e.to, e.dat, GetRevEdge(&e)->dat);
}
}
}
return ret;
}
bool hasNegativeCycle() {
vector<int> s(n);
Ls d;
for (int i=0; i<n; i++) s[i] = i;
return SPFA(s, d);
}
// return true if the graph has a negative cycle
bool FloydWarshall(vector<Ls> &ds) {
if (cost.empty()) CreateAdjMat();
ds = vector<Ls>(cost);
for (int i=0; i<n; i++) {
ds[i][i] = min(ds[i][i], Len(0));
}
for (int k=0; k<n; k++) {
for (int i=0; i<n; i++) {
if (ds[i][k] == INF) continue;
for (int j=0; j<n; j++) {
if (ds[k][j] == INF) continue;
Len nd = max(ds[i][k] + ds[k][j], -INF);
if (ds[i][j] > nd) {
ds[i][j] = nd;
}
}
}
}
for (int i=0; i<n; i++) {
if (ds[i][i] < 0) return true;
}
return false;
}
// Karp's Algorithm O(NM)
// should be tested
// should be used for SCC
double MinimumMeanCycle() {
vector<Ls> dp(n+1, Ls(n, INF));
dp[0][0] = 0;
for (int i=1; i<=n; i++) {
for (int v=0; v<n; v++) {
for (auto &e : es[v]) {
int u = e.to;
dp[i][u] = min(dp[i][u], dp[i-1][v] + e.dat.len);
}
}
}
double ret = 1.0/0.0;
for (int v=0; v<n; v++) {
double alpha = (-1.0)/0.0;
for (int i=1; i<n; i++) {
if (dp[n][v] == INF) continue;
if (dp[i][v] == INF) continue;
alpha = max(alpha, (dp[n][v]-dp[i][v])/double(n-i));
}
ret = min(ret, alpha);
}
return ret;
}
Len Dinic(int s, int t) {
vector<int> level, iter;
vector<bool> sweep_res;
function<Len(int,int,Len)> dfs;
dfs = [&](int s, int u, Len crr) {
if (s == u || crr == 0) return crr;
Len sum = 0;
while (1) {
auto &ues = sweep_res[u] ? res[u] : es[u];
for (int &i=iter[u]; i<ues.size(); i++) {
Edge *e = &ues[i];
Edge *re = GetRevEdge(e);
int v = e->to;
if (level[v] >= level[u] || re->dat.cap <= 0) continue;
Len f = dfs(s, v, min(crr-sum, re->dat.cap));
if (f <= 0) continue;
re->dat.cap -= f;
e->dat.cap += f;
sum += f;
if (sum >= crr) break;
}
if (sweep_res[u] && iter[u] == ues.size()) break;
if (iter[u] == ues.size() && !sweep_res[u]) {
sweep_res[u] = true;
iter[u] = 0;
}
}
return sum;
};
vector<int> q(n);
Len flow = 0;
while (1) {
level.assign(n, -1);
int ql = 0;
int qr = 0;
level[ q[qr++] = s ] = 0;
while (ql != qr && level[t] == -1) {
int u = q[ql++];
for (auto &e : es[u]) {
if (e.dat.cap > 0 && level[e.to] == -1) {
level[ q[qr++] = e.to ] = level[u] + 1;
}
}
for (auto &e : res[u]) {
if (e.dat.cap > 0 && level[e.to] == -1) {
level[ q[qr++] = e.to ] = level[u] + 1;
}
}
}
if (level[t] == -1) return flow;
iter.assign(n, 0);
sweep_res.assign(n, false);
flow += dfs(s, t, INF);
}
}
//Len Fujishige
};
template<class Data=DefData>
struct DFSForest {
using G = Graph<Data>;
using Edge = typename G::Edge;
using Brid = pair<int, Edge*>;
int grp;
vector<int> ord;
vector<int> low;
vector<int> belong;
vector<int> artic;
vector<Brid> bridge;
DFSForest() {}
DFSForest(G &g, bool is_directed) {
Init(g, is_directed);
}
void Init(G &g, bool is_directed) {
int k = 0;
int idx = 0;
int n = g.n;
vector<int> st(n);
grp = 0;
ord.resize(n, -1);
low.resize(n);
belong.resize(n, -1);
function<void(int,int,Edge*)> dfs;
// to deal with multiple edges, it uses a pointer
auto update = [&](int v, Edge *e, bool &is_artic, int &cnt) {
int u = e->to;
if (ord[u] != -1) {
if (belong[u] == -1) low[v] = min(low[v], ord[u]);
} else {
cnt++;
dfs(u, v, e);
low[v] = min(low[v], low[u]);
if (ord[v] <= low[u]) is_artic = true;
if (ord[v] < low[u]) bridge.emplace_back(Brid(v, e));
}
};
dfs = [&](int v, int p, Edge *par) {
bool is_artic = false;
int cnt = 0;
st[idx++] = v;
low[v] = ord[v] = k++;
for (auto &e : g.es[v]) {
if (g.GetRevEdge(&e) == par) continue;
update(v, &e, is_artic, cnt);
}
if (!is_directed) {
for (auto &e : g.res[v]) {
if (g.GetRevEdge(&e) == par) continue;
update(v, &e, is_artic, cnt);
}
}
if (p == -1) is_artic = (cnt > 1);
if (is_artic) artic.emplace_back(v);
if (low[v] != ord[v]) return;
while (1) {
int u = st[--idx];
belong[u] = grp;
if (u == v) break;
}
grp++;
};
for (int i=0; i<n; i++) {
if (ord[i] == -1) dfs(i, -1, NULL);
}
}
};
template<class Data=DefData>
struct SCCData {
using VD = typename Data::VData;
using ED = typename Data::EData;
using GD = typename Data::GData;
using G = Graph<Data>;
using Len = int;
struct VData {
G g; // the graph consisting of contracted nodes in one component
vector<int> cont2orig; // the correspondence of the node index: v on SCCVData::g -> cont2orig[v] on the original graph(G)
};
struct EData : ED {
int s;
int t;
EData(int a, int b, const ED &dat) : ED(dat), s(a), t(b) {}
};
struct GData {
vector<int> orig2cont; // the correspondence of the node index: v on G -> orig2cont[v] on G's SCC::vdat[belong[v]].g
};
static const Len INF = 0x33433433;
};
template<class Data=DefData>
struct SCC : Graph<SCCData<Data> > {
using ED = typename Data::EData;
using EData = typename SCCData<Data>::EData;
using G = Graph<Data>;
DFSForest<Data> df;
SCC(G &g) : df(g, true) {
int n = g.n;
this->Init(df.grp);
auto &gdat = this->gdat;
auto &vdat = this->vdat;
gdat.orig2cont.resize(n);
for (int v=0; v<n; v++) {
auto &vd = vdat[df.belong[v]];
gdat.orig2cont[v] = vd.cont2orig.size();
vd.cont2orig.emplace_back(v);
}
for (int i=0; i<df.grp; i++) {
auto &vd = vdat[i];
vd.g.Init(vd.cont2orig.size());
}
for (int v=0; v<n; v++) {
for (auto &e : g.es[v]) {
int u = e.to;
ED &rd = g.GetRevEdge(&e)->dat;
int bv = df.belong[v];
int bu = df.belong[u];
if (bv == bu) {
auto &vd = vdat[bv];
auto &dic = gdat.orig2cont;
vd.g.AddEdge(dic[v], dic[u], e.dat, rd);
} else {
this->AddEdge(bv, bu, EData(v, u, e.dat), EData(u, v, rd));
}
}
}
}
};
using LLI = long long int;
typedef DefData A;
typedef Graph<A> G;
typedef DFSForest<A> D;
int N;
int M;
G g;
D d;
bool used[114514];
int ord[114514];
deque<int> ans, ans2;
deque<int> dfs(int v, int ig=0) {
deque<int> ret;
for (auto &e : g.es[v]) {
int u = e.to;
if (d.ord[u] < d.ord[v]) continue;
if (ig == 0) ret = dfs(u);
ig--;
}
ret.emplace_back(v);
return ret;
}
int dfs2(int v) {
int num_child = 0;
bool to_root = false;
for (auto &e : g.es[v]) {
int u = e.to;
if (u == 0) to_root = true;
if (ord[u] < ord[v]) continue;
num_child++;
}
int exc_u;
int type = 0;
for (auto &e : g.es[v]) {
int u = e.to;
if (ord[u] < ord[v]) continue;
//printf("%d -> %d\n", v, u);
type = dfs2(u);
if (type == 1) {
exc_u = u;
break;
} else if (type == 2) break;
}
//if (type == 1) printf("v: %d exc_u: %d num_child: %d\n", v, exc_u, num_child);
if (type == 1 && num_child >= 2) {
//printf("branch: %d\n", v);
for (auto &e : g.es[v]) {
int u = e.to;
if (ord[u] < ord[v]) continue;
if (u == exc_u) continue;
//printf("toward: %d\n", u);
ans2 = dfs(u);
reverse(ans2.begin(), ans2.end());
break;
}
type = 2;
}
if (type == 0 && num_child == 0 && to_root) {
type = 1;
//printf("found: %d\n", v);
}
if (type == 1) {
ans.emplace_front(v);
} else if (type == 2) {
ans2.emplace_front(v);
}
return type;
}
deque<int> dfs3(int v, int ig=0) {
deque<int> ret;
used[v] = true;
for (auto &e : g.es[v]) {
int u = e.to;
if (used[u]) continue;
if (ig == 0) {
ret = dfs3(u);
break;
} else dfs3(u, -1);
ig--;
}
ret.emplace_back(v);
return ret;
}
void dfs4(int v, int p) {
ord[v] = ord[p]+1;
for (auto &e : g.es[v]) {
int u = e.to;
if (ord[u] != -1) continue;
dfs4(u, v);
}
}
int main() {
scanf("%d%d", &N, &M);
g.Init(N);
for (int i=0; i<M; i++) {
int a, b;
scanf("%d%d", &a, &b);
--a;
--b;
g.AddEdge(a, b);
g.AddEdge(b, a);
}
d.Init(g, true);
/*printf("artic: ");
for (auto v : d.artic) {
printf("%d ", v);
}puts("");*/
if (!d.artic.empty()) {
ans = dfs3(d.artic[0]);
//for (auto v : ans) printf("%d ", v);
//puts("");
fill(used, used+N, false);
ans2 = dfs3(d.artic[0], 1);
//for (auto v : ans2) printf("%d ", v);
//puts("");
ans2.pop_back();
reverse(ans2.begin(), ans2.end());
ans.insert(ans.end(), ans2.begin(), ans2.end());
} else if (g.es[0].size() <= 1) {
ans = dfs(0);
} else {
for (int i=0; i<N; i++) {
fill(ord, ord+N, -1);
dfs4(i, i);
dfs2(i);
ans.insert(ans.end(), ans2.begin(), ans2.end());
if (!ans.empty()) break;
}
}
printf("%d\n", (int)ans.size());
for (int v : ans) {
printf("%d ", v+1);
}
puts("");
}
Submission Info
Submission Time |
|
Task |
B - Hamiltonish Path |
User |
potetisensei |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
15432 Byte |
Status |
WA |
Exec Time |
219 ms |
Memory |
100720 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:636:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
^
./Main.cpp:640:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
70 ms |
18432 KB |
subtask_1_02.txt |
AC |
14 ms |
3968 KB |
subtask_1_03.txt |
AC |
104 ms |
44660 KB |
subtask_1_04.txt |
AC |
92 ms |
37948 KB |
subtask_1_05.txt |
AC |
93 ms |
38844 KB |
subtask_1_06.txt |
AC |
80 ms |
19388 KB |
subtask_1_07.txt |
AC |
88 ms |
17152 KB |
subtask_1_08.txt |
AC |
94 ms |
17280 KB |
subtask_1_09.txt |
AC |
219 ms |
100720 KB |
subtask_1_10.txt |
WA |
14 ms |
5632 KB |
subtask_1_11.txt |
WA |
17 ms |
6144 KB |
subtask_1_12.txt |
AC |
1 ms |
256 KB |
subtask_1_13.txt |
AC |
1 ms |
256 KB |