이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<long long> vl;
typedef pair<long long, long long > pl;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18
#define MIN -1e18
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll N , n, m, mid, res,pos, mn, mx, sum, h1, h2, arr[3234567],arr1[1234567],k, i, j, h, a, x, y, z,par[1234567],ans;
bool used[1234567];
ll tp[1234567];
ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123];
//ll jump[22][223456];
//ll lvl[1234567];
//ll bit[1234567];
//ll timer;
//ll st[1234567],endd[1234567];
//ll dp[5005][5005];
vl edge[1234567],bcc_graph[1234567],stck;
ll low[1234567] , timer=0 , disc[1234567],bccs=1;
void dfs1(ll node,ll par=0){
low[node] = disc[node] = timer++;
//set timer
stck.pb(node);
N++;
for(auto u:edge[node]){
if(u!=par){
if(disc[u]){
low[node] = min(low[node] , disc[u]);
//find low
}
else{
dfs1(u,node);
low[node] = min(low[node] , low[u]);
if(low[u] >= disc[node]){
//here is articular point
//connect edge
bcc_graph[node].pb(n+bccs);
//make biconnected graph
while(!bcc_graph[n+bccs].size() || bcc_graph[n+bccs].back()!=u){
bcc_graph[n+bccs].pb(stck.back());
stck.pop_back();
}
bccs++;
}
}
}
}
}
ll sz[1234567];
void dfs2(ll node){
//cout<<node<<'\n';
sz[node] = (node<=n);
for(auto u:bcc_graph[node]){
dfs2(u);
sz[node]+=sz[u];
if(node > n){
ans -= bcc_graph[node].size()*(sz[u])*(sz[u]-1);
}
}
if(node>n){
ans-= bcc_graph[node].size()*(N-sz[node])*(N-sz[node]-1);
}
}
class A {
public :
static void funcA() {
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y;
edge[x].pb(y);
edge[y].pb(x);
}
for(int i=1;i<=n;i++){
if(disc[i]==0){
N=0;
dfs1(i);
ans += N*(N-1)*(N-2);
dfs2(i);
}
}
cout<<ans;
}
}lol;
void solve() {
A::funcA();
}
int main() {
ll T = 1;
//cin>>T;
boost;
while (T--) {
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |