oj.uz

Submission #320124

# Submission time Handle Problem Language Result Execution time Memory
320124 2020-11-07T16:08:42 Z AmineWeslati Duathlon (APIO18_duathlon) C++14
31 / 100
 1000 ms 1048580 KB 
//Never stop trying
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
#define int ll
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 2e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}

#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int N,M;
vi adj[MX];

bool sub3(){
	FOR(i,1,N+1) if(sz(adj[i])>2) return 0;
	return 1;
}

bool vis[MX]; 
vi vv;
ll ans=0;

ll sub[MX];
void dfs(int u, int p){
	vis[u]=1; vv.pb(u);
	sub[u]=1;

	ll sum=0; 
	for(auto v: adj[u]) if(v!=p){
		dfs(v,u);
		sub[u]+=sub[v];
		sum+=sub[v];
	}
	for(auto v: adj[u]) if(v!=p) ans+=(sum-sub[v])*sub[v];
}

int ed=0;

void dfs2(int u){
	vis[u]=true; vv.pb(u);
	ed+=sz(adj[u]);
	for(auto v: adj[u]){
		if(!vis[v]) dfs2(v);
	}
}

int32_t main() {
    boost; IO();

    cin>>N>>M;
    FOR(i,0,M){
    	int u,v; cin>>u>>v;
    	adj[u].pb(v); 
    	adj[v].pb(u);
    }

    if(sub3()){
    	FOR(i,1,N+1) vis[i]=false;
	    FOR(u,1,N+1) if(!vis[u]){
	    	vv.clear(); ed=0;
	    	dfs2(u);  
	    	ed/=2;
	    	int n=sz(vv); //dbgs(n,ed); 
	    	if(ed==n-1){
	    		FOR(x,1,n-2+1) ans+=2*x*(n-1-x);
	    	}
	    	else{
	    		ans+=n*(n-1)*(n-2);
	    	}
	    }
    }
    else{
	    FOR(i,1,N+1) vis[i]=false;
	    FOR(root,1,N+1) if(!vis[root]){
	    	vv.clear();
	    	dfs(root,root);
	    	for(auto u: vv) ans+=2*(sub[u]-1)*(sz(vv)-sub[u]);
	    }
    }
    cout << ans << endl;
    

    return 0;
}

/* Careful!!!
    .Array bounds
    .Infinite loops
    .Uninitialized variables / empty containers
    .Multisets are shit

   Some insights:
    .Binary search
    .Graph representation
    .Write brute force code
    .Change your approach
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 694 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 694 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 13912 KB Output is correct
2 Correct 78 ms 13920 KB Output is correct
3 Correct 65 ms 11120 KB Output is correct
4 Correct 67 ms 13788 KB Output is correct
5 Correct 63 ms 11744 KB Output is correct
6 Correct 67 ms 11744 KB Output is correct
7 Correct 69 ms 10848 KB Output is correct
8 Correct 66 ms 11228 KB Output is correct
9 Correct 66 ms 10408 KB Output is correct
10 Correct 74 ms 10720 KB Output is correct
11 Correct 49 ms 9316 KB Output is correct
12 Correct 48 ms 9196 KB Output is correct
13 Correct 46 ms 9064 KB Output is correct
14 Correct 45 ms 9068 KB Output is correct
15 Correct 39 ms 8548 KB Output is correct
16 Correct 34 ms 8292 KB Output is correct
17 Correct 5 ms 5132 KB Output is correct
18 Correct 5 ms 5228 KB Output is correct
19 Correct 5 ms 5100 KB Output is correct
20 Correct 5 ms 5228 KB Output is correct
21 Correct 5 ms 5228 KB Output is correct
22 Correct 5 ms 5120 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 5 ms 5100 KB Output is correct
6 Correct 5 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 5 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 4 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 5 ms 5228 KB Output is correct
14 Correct 4 ms 5248 KB Output is correct
15 Correct 4 ms 5100 KB Output is correct
16 Correct 4 ms 5228 KB Output is correct
17 Correct 4 ms 5100 KB Output is correct
18 Correct 4 ms 5100 KB Output is correct
19 Correct 4 ms 5228 KB Output is correct
20 Correct 4 ms 5100 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 10844 KB Output is correct
2 Correct 65 ms 10844 KB Output is correct
3 Correct 62 ms 10844 KB Output is correct
4 Correct 64 ms 10844 KB Output is correct
5 Correct 64 ms 10844 KB Output is correct
6 Correct 69 ms 11996 KB Output is correct
7 Correct 72 ms 13400 KB Output is correct
8 Correct 73 ms 12768 KB Output is correct
9 Correct 70 ms 12124 KB Output is correct
10 Correct 66 ms 10340 KB Output is correct
11 Correct 62 ms 10972 KB Output is correct
12 Correct 64 ms 10212 KB Output is correct
13 Correct 61 ms 10028 KB Output is correct
14 Correct 58 ms 9444 KB Output is correct
15 Correct 54 ms 9392 KB Output is correct
16 Correct 31 ms 8300 KB Output is correct
17 Correct 44 ms 11360 KB Output is correct
18 Correct 44 ms 10968 KB Output is correct
19 Correct 45 ms 10964 KB Output is correct
20 Correct 45 ms 11220 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5228 KB Output is correct
3 Runtime error 937 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 11164 KB Output is correct
2 Correct 71 ms 10844 KB Output is correct
3 Execution timed out 1053 ms 1048580 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 694 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 694 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -