oj.uz

Submission #320123

# Submission time Handle Problem Language Result Execution time Memory
320123 2020-11-07T16:02:06 Z AmineWeslati Duathlon (APIO18_duathlon) C++14
23 / 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);
	for(auto v: adj[u]){
		ed++;
		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();
	    	dfs2(u); ed/=2;
	    	int n=sz(vv);
	    	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 746 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 746 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 13912 KB Output is correct
2 Correct 84 ms 15096 KB Output is correct
3 Incorrect 71 ms 12380 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 4 ms 5152 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 4 ms 5132 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 4 ms 5100 KB Output is correct
14 Correct 5 ms 5100 KB Output is correct
15 Correct 4 ms 5100 KB Output is correct
16 Correct 4 ms 5100 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 67 ms 10844 KB Output is correct
2 Correct 68 ms 10840 KB Output is correct
3 Correct 81 ms 10940 KB Output is correct
4 Correct 65 ms 10972 KB Output is correct
5 Correct 71 ms 10844 KB Output is correct
6 Correct 87 ms 11996 KB Output is correct
7 Correct 92 ms 13400 KB Output is correct
8 Correct 103 ms 12760 KB Output is correct
9 Correct 70 ms 12124 KB Output is correct
10 Correct 63 ms 10336 KB Output is correct
11 Correct 69 ms 11100 KB Output is correct
12 Correct 76 ms 10212 KB Output is correct
13 Correct 62 ms 10084 KB Output is correct
14 Correct 81 ms 9524 KB Output is correct
15 Correct 56 ms 9196 KB Output is correct
16 Correct 34 ms 8420 KB Output is correct
17 Correct 56 ms 11344 KB Output is correct
18 Correct 50 ms 10964 KB Output is correct
19 Correct 47 ms 10968 KB Output is correct
20 Correct 49 ms 11092 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 5 ms 5100 KB Output is correct
3 Runtime error 955 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 71 ms 10844 KB Output is correct
2 Correct 68 ms 10716 KB Output is correct
3 Execution timed out 1136 ms 997692 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 746 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 746 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -