oj.uz

Submission #106047

# Submission time Handle Problem Language Result Execution time Memory
106047 2019-04-16T09:57:47 Z username Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1049600 KB 
#pragma GCC optimize("O3")
#include<stdint.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define VIS(it,con) for(auto it=con.begin();it!=con.end();++it)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define MIN(x,y) (x=min(x,(y)))
#define MAX(x,y) (x=max(x,(y)))
#define mid ((l+r)/2)
#define lch (idx*2+1)
#define rch (idx*2+2)
/*****************************************************************************/
#include<bits/stdc++.h>
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> VI;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define RREP(i,j,k) for(register int i=(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define MST(a,v) memset(a,(v),sizeof a)
#define pb push_back
#define F first
#define S second
#define endl '\n'
//																#define __debug
#ifdef __debug
	#define IOS (void)0
	#define de(...) cerr<<__VA_ARGS__
	#define ar(a,s,t) {REP(__i,s,t)de(min((int)1e9-1,a[__i])<<' ');de(endl);}
#else
	#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
	#define de(...) (void)0
	#define ar(...) (void)0
#endif
/***********************************default***********************************/
const int maxn=1e5+9;
int n,m,res=0,sum,sz[maxn];
VI G[maxn];

void dfs(int u,int f){
	sz[u]=1;
	++sum;
	REP(i,0,G[u].size()){
		int v=G[u][i];
		if(v==f)continue;
		dfs(v,u);
		sz[u]+=sz[v];
	}
}

void calc(int u,int f){
	REP(i,0,G[u].size()){
		int v=G[u][i];
		if(v==f){
			res+=(sz[u]-1)*(sum-sz[u]);
			continue;
		}
		calc(v,u);
		res+=sz[v]*(sum-sz[v]-1);
	}
}

main(){
	IOS;
	cin>>n>>m;
	REP(i,0,m){
		int u,v;cin>>u>>v,--u,--v;
		G[u].pb(v),G[v].pb(u);
	}
	MST(sz,-1);
	REP(i,0,n)if(sz[i]<0){
		sum=0;
		dfs(i,-1);
		calc(i,-1);
	}
	cout<<res<<endl;
}

Compilation message

count_triplets.cpp: In function 'void dfs(int_fast64_t, int_fast64_t)':
count_triplets.cpp:23:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
count_triplets.cpp:49:2: note: in expansion of macro 'REP'
  REP(i,0,G[u].size()){
  ^~~
count_triplets.cpp: In function 'void calc(int_fast64_t, int_fast64_t)':
count_triplets.cpp:23:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
count_triplets.cpp:58:2: note: in expansion of macro 'REP'
  REP(i,0,G[u].size()){
  ^~~
count_triplets.cpp: At global scope:
count_triplets.cpp:69:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1184 ms 1037148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1184 ms 1037148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 105748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7744 KB Output is correct
2 Correct 101 ms 8548 KB Output is correct
3 Correct 90 ms 8312 KB Output is correct
4 Correct 95 ms 8424 KB Output is correct
5 Correct 101 ms 8424 KB Output is correct
6 Correct 137 ms 9248 KB Output is correct
7 Correct 116 ms 9444 KB Output is correct
8 Correct 115 ms 9216 KB Output is correct
9 Correct 116 ms 9052 KB Output is correct
10 Correct 92 ms 8444 KB Output is correct
11 Correct 80 ms 8496 KB Output is correct
12 Correct 101 ms 8440 KB Output is correct
13 Correct 91 ms 8440 KB Output is correct
14 Correct 80 ms 8184 KB Output is correct
15 Correct 67 ms 7672 KB Output is correct
16 Correct 52 ms 6520 KB Output is correct
17 Correct 59 ms 8684 KB Output is correct
18 Correct 57 ms 8680 KB Output is correct
19 Correct 64 ms 8544 KB Output is correct
20 Correct 73 ms 8552 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3556 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Execution timed out 1123 ms 1049600 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7800 KB Output is correct
2 Correct 117 ms 8332 KB Output is correct
3 Execution timed out 1159 ms 746932 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1184 ms 1037148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1184 ms 1037148 KB Time limit exceeded
2 Halted 0 ms 0 KB -