제출 #1260813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260813		_rain_	철인 이종 경기 (APIO18_duathlon)	C++20	31 / 100	40 ms	15940 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(s) (int)(s).size()
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask,x) (((mask)>>(x))&(1))

template<class X,class Y>
	bool maximize(X &x ,Y y){
		if (x < y) return x = y , true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x ,Y y){
		if (x > y) return x = y , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
		return;
	}
template<class X,class Y>
	Y Find(vector<X>&data,Y y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}
	
const int N = (int) 1e5;
const int M = (int) 2e5;
	int x[M + 2] , y[M + 2];
	int n , m;
	vector<int>ke[N + 2];
		void add_canh(int u , int v){
			ke[u].push_back(v) , ke[v].push_back(u);
			return;
		}
		
namespace subtask1{
	bool check(){
		return true;
	}
	
	int sub[N + 2] = {};
	int vis[N + 2] = {} , color[N + 2] = {};
	int dp[N + 2] = {};
	LL ways[N + 2][2] = {};
	LL ans = 0 , cnt = 0 , tmp = 0;
		
		void pre_dfs(int u , int p){
			sub[u] = 1;
			vis[u] = 1;
			dp[u] = dp[p] + 1;
			++cnt;
			for(auto& v : ke[u]){
				if (v == p) continue;
				if (vis[v] == 0){
					pre_dfs(v , u);
					sub[u] += sub[v];
				}
			}
			return;
		}
		
		void dfs(int u , int p){
			color[u] = 1;
//			cout << u << ' ' << p << '\n';
			for(auto& v : ke[u]){
				if (v == p) continue;
				if (color[v] == 2) continue;
				if (color[v]==1) {
					LL length = dp[u] - dp[v] + 1;
					LL w1 = (LL)length * (length - 1) * (length - 2) / 6;
					w1 = w1 * 2;
					assert(length);
					LL w2 = length * (length - 1) / 2 * (cnt - length);
					w2 -= (length - 1) * (dp[v] - 1);
					w2 -= (length - 1) * (sub[u] - 1);
					
					tmp = tmp + (w1 + w2) * 2;
					
					continue;
				}
				ans += (LL)sub[v] * (cnt - sub[v]);
				dfs(v,u);
			}
			color[u] = 2;
			return;
		}
		
	void main_code(){
		LL res = 0;
		for(int i = 1; i <= n; ++i) if (!vis[i]){
			ans = 0;
			cnt = 0;
			pre_dfs(i,0);
			dfs(i,0);
			ans -= (LL)cnt*(cnt-1)/2;
			ans *= 2;
			res += ans;
		}
		cout << res + tmp;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}	
			
		cin >> n >> m;
		for(int i = 1; i <= m; ++i) {
			cin >> x[i] >> y[i];
			add_canh(x[i] , y[i]);
		}
		if (subtask1::check()) return subtask1::main_code() , false;
		assert(false);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:111:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:112:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10