oj.uz

Submission #265223

# Submission time Handle Problem Language Result Execution time Memory
265223 2020-08-14T14:06:02 Z kaage Duathlon (APIO18_duathlon) C++17
23 / 100
 313 ms 23544 KB 
#line 2 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp"
#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx2")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define all(V) V.begin(),V.end()
typedef long long lint;
typedef unsigned long long ulint;
typedef std::pair<int, int> P;
typedef std::pair<lint, lint> LP;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;
constexpr double eps = DBL_EPSILON;
constexpr double PI=3.141592653589793238462643383279;
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
inline lint gcd(lint a, lint b) {
	while (b) {
		lint c = a;
		a = b; b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) {
	return a / gcd(a, b) * b;
}
bool isprime(lint n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
template<typename T>
T mypow(T a, lint b) {
	T res(1);
	while(b){
		if(b&1)res*=a;
		a*=a;
		b>>=1;
	}
	return res;
}
lint modpow(lint a, lint b, lint m) {
	lint res(1);
	while(b){
		if(b&1){
			res*=a;res%=m;
		}
		a*=a;a%=m;
		b>>=1;
	}
	return res;
}
template<typename T>
void printArray(std::vector<T>& vec) {
	rep(i, vec.size()){
		std::cout << vec[i];
		std::cout<<(i==(int)vec.size()-1?"\n":" ");
	}
}
template<typename T>
void printArray(T l, T r) {
	T rprev = std::prev(r);
	for (T i = l; i != rprev; i++) {
		std::cout << *i << " ";
	}
	std::cout << *rprev << std::endl;
}
LP extGcd(lint a,lint b) {
	if(b==0)return {1,0};
	LP s=extGcd(b,a%b);
	std::swap(s.first,s.second);
	s.second-=a/b*s.first;
	return s;
}
LP ChineseRem(const lint& b1,const lint& m1,const lint& b2,const lint& m2) {
	lint p=extGcd(m1,m2).first;
	lint tmp=(b2-b1)*p%m2;
	lint r=(b1+m1*tmp+m1*m2)%(m1*m2);
	return std::make_pair(r,m1*m2);
}
/*template<typename F>
inline constexpr decltype(auto) lambda_fix(F&& f){
	return [f=std::forward<F>(f)](auto&&... args){
		return f(f,std::forward<decltype(args)>(args)...);
	};
}*/
#line 3 "/Users/kaage/Desktop/ProgrammingWorkspace/library/graph/UnionFind.hpp"
class UnionFind {
protected:
	std::vector<int> par, size;
public:
	UnionFind(){}
	UnionFind(int size) {init(size);}
	void init(int size){
		par.resize(size); this->size.resize(size, 1);
		rep(i, size) {
			par[i] = i;
		}
	}
	int find(int n) {
		if (par[n] == n)return n;
		return par[n] = find(par[n]);
	}
	void unite(int n, int m) {
		n = find(n);
		m = find(m);
		if (n == m)return;
		int a=n,b=m;
		if(size[a]>size[b])std::swap(a,b);
		par[a] = b;
		size[b] += size[a];
	}
	bool same(int n, int m) {
		return find(n) == find(m);
	}
	int getsize(int n) {
		return size[find(n)];
	}
};
#line 3 "main.cpp"
int n,m,u[110],v[110],cnt,sz[100010];
lint ans;
std::vector<int> vec[100010],vec2[100010];
bool used[100010];
UnionFind uf;
void dfs(int node){
	used[node]=true;
	sz[node]=1;
	for(int i:vec[node]){
		if(!used[i]){
			dfs(i);
			sz[node]+=sz[i];
			vec2[node].push_back(sz[i]);
		}
	}
	if(node!=1)vec2[node].push_back(uf.getsize(node)-sz[node]);
	lint sum=0;
	for(int i:vec2[node]){
		ans+=sum*i;
		sum+=i;
	}
}
int main(){
	std::cin>>n>>m;
	uf.init(n+1);
	rep(i,m){
		int u,v;
		std::cin>>u>>v;
		vec[u].emplace_back(v);
		vec[v].emplace_back(u);
		uf.unite(u,v);
	}
	REP(i,n){
		if(!used[i])dfs(i);
	}
	std::cout<<ans*2<<std::endl;
}

Compilation message

/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:3: warning: ignoring #pragma target  [-Wunknown-pragmas]
/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:4: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:5: warning: ignoring #pragma optimize  [-Wunknown-pragmas]

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 313 ms 23544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 12768 KB Output is correct
2 Correct 218 ms 12720 KB Output is correct
3 Correct 222 ms 12768 KB Output is correct
4 Correct 243 ms 12828 KB Output is correct
5 Correct 222 ms 12768 KB Output is correct
6 Correct 249 ms 18540 KB Output is correct
7 Correct 262 ms 16544 KB Output is correct
8 Correct 252 ms 15516 KB Output is correct
9 Correct 230 ms 14600 KB Output is correct
10 Correct 223 ms 12756 KB Output is correct
11 Correct 242 ms 13576 KB Output is correct
12 Correct 228 ms 13684 KB Output is correct
13 Correct 225 ms 13560 KB Output is correct
14 Correct 182 ms 13436 KB Output is correct
15 Correct 175 ms 13304 KB Output is correct
16 Correct 111 ms 12408 KB Output is correct
17 Correct 160 ms 14196 KB Output is correct
18 Correct 162 ms 14064 KB Output is correct
19 Correct 157 ms 14316 KB Output is correct
20 Correct 163 ms 14072 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 5 ms 5120 KB Output is correct
3 Incorrect 5 ms 5120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 12792 KB Output is correct
2 Correct 193 ms 12792 KB Output is correct
3 Incorrect 217 ms 12700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -