| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 51072 | 2018-06-16T02:51:06 Z | yp155136 | Duathlon (APIO18_duathlon) | C++14 | 410 ms | 185532 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 800006;
int e[N];
vector<int> G[N];
int dfn_clock[N];
int stamp=0;
bool vis[N];
int low[N];
stack<int> sta;
vector<int> bcc[N];
vector<int> vv[N];
int bcc_no = 0;
void dfs(int now,int par)
{
//cout << "now = " << now << " , par = " << par <<endl;
dfn_clock[now] = low[now] = (++stamp);
vis[now] = true;
for (int i:G[now])
{
int to = (e[i]^now);
if (to == par) continue;
if (!vis[to])
{
sta.push(i);
dfs(to,now);
low[now] = min(low[now],low[to]);
if (low[to] >= dfn_clock[now])
{
bcc_no++;
int p;
do {
p = sta.top();
bcc[bcc_no].push_back(p);
sta.pop();
} while (p != i);
}
}
else if (dfn_clock[to] < dfn_clock[now])
{
sta.push(i);
low[now] = min(low[now],dfn_clock[to]);
}
}
}
typedef long long LL;
LL ans=0;
int cnt[N];
int in_bcc[N];
int type[N];
int sz[N];
int n,m;
int vis2[N];
int vis_id = 880301;
int xx[N],yy[N];
vector<int> G2[N];
int subtree_sz[N];
void dfs2(int now,int par)
{
subtree_sz[now] = sz[now];
for (int i:G2[now])
{
if(i != par)
{
dfs2(i,now);
subtree_sz[now] += subtree_sz[i];
}
}
}
void dfs3(int now,int par)
{
if (type[now] == 2)
{
//cout << "now = " << now << endl;
//cut vertex
for (int i:G2[now])
{
ans += (sz[i]*1LL*(sz[i]-1));
//cout << "ans = " << ans << endl;
}
//two different
vector<int> szz;
for (int i:G2[now])
{
if (subtree_sz[i] >= subtree_sz[now])
{
szz.push_back(n - subtree_sz[now]);
}
else
{
szz.push_back(subtree_sz[i]);
}
}
LL tot=0,tot2=0;
for (int i:szz)
{
tot += i;
tot2 += i*1LL*i;
}
ans += (tot*tot-tot2);
//cout << "ans = " << ans << endl;
}
else if (type[now] == 1)
{
;
}
for (int i:G2[now])
{
if (i != par)
{
dfs3(i,now);
}
}
}
int main ()
{
scanf("%d %d",&n,&m);
for (int i=1;i<=m;++i)
{
int x,y;
scanf("%d %d",&x,&y);
e[i] = (x^y);
G[x].push_back(i);
G[y].push_back(i);
xx[i] = x;
yy[i] = y;
}
dfs(1,1);
/*for (int i=1;bcc_no>=i;i++)
{
cout << "i = " << i << " : ";
for (int j:bcc[i]) cout << j << ' ';
cout << endl;
}*/
assert(bcc_no == m);
for (int i=1;i<=bcc_no;++i)
{
++vis_id;
vector<int> v;
for (int j:bcc[i])
{
if (vis2[ xx[j] ] != vis_id)
{
v.push_back(xx[j]);
vis2[ xx[j] ] = vis_id;
}
if (vis2[ yy[j] ] != vis_id)
{
v.push_back(yy[j]);
vis2[ yy[j] ] = vis_id;
}
}
for (int j:v)
{
cnt[j]++;
}
vv[i] = v;
}
int vid = n;
for (int i=1;i<=bcc_no;++i)
{
++vid;
type[vid] = 1;
for (int j:vv[i])
{
if (cnt[j] == 1)
{
sz[vid]++;
}
else
{
G2[vid].push_back(j);
G2[j].push_back(vid);
type[j] = 2;
sz[j] = 1;
}
}
}
dfs2(vid,vid);
dfs3(vid,vid);
printf("%lld\n",ans);
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 144 ms | 150964 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 144 ms | 150964 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 248 ms | 181764 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 64 ms | 181764 KB | Output is correct |
| 2 | Correct | 65 ms | 181764 KB | Output is correct |
| 3 | Correct | 64 ms | 181764 KB | Output is correct |
| 4 | Correct | 83 ms | 181764 KB | Output is correct |
| 5 | Correct | 64 ms | 181764 KB | Output is correct |
| 6 | Correct | 64 ms | 181764 KB | Output is correct |
| 7 | Correct | 67 ms | 181764 KB | Output is correct |
| 8 | Correct | 66 ms | 181764 KB | Output is correct |
| 9 | Correct | 68 ms | 181764 KB | Output is correct |
| 10 | Runtime error | 164 ms | 181764 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 304 ms | 181764 KB | Output is correct |
| 2 | Correct | 309 ms | 181764 KB | Output is correct |
| 3 | Correct | 299 ms | 181764 KB | Output is correct |
| 4 | Correct | 266 ms | 181764 KB | Output is correct |
| 5 | Correct | 287 ms | 181764 KB | Output is correct |
| 6 | Correct | 353 ms | 185532 KB | Output is correct |
| 7 | Correct | 345 ms | 185532 KB | Output is correct |
| 8 | Correct | 357 ms | 185532 KB | Output is correct |
| 9 | Correct | 410 ms | 185532 KB | Output is correct |
| 10 | Runtime error | 232 ms | 185532 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 67 ms | 185532 KB | Output is correct |
| 2 | Correct | 75 ms | 185532 KB | Output is correct |
| 3 | Runtime error | 157 ms | 185532 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 298 ms | 185532 KB | Output is correct |
| 2 | Correct | 311 ms | 185532 KB | Output is correct |
| 3 | Runtime error | 295 ms | 185532 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 144 ms | 150964 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 144 ms | 150964 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |