oj.uz

Submission #172195

# Submission time Handle Problem Language Result Execution time Memory
172195 2019-12-31T14:44:37 Z dndhk Duathlon (APIO18_duathlon) C++14
0 / 100
 271 ms 37684 KB 
#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 0
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 100000;

int N, M, NN;
vector<int> gp[MAX_N+1];
int dfsn[MAX_N+1], up[MAX_N+1], p[MAX_N+1], cnt, pcnt=1;
int sz2[MAX_N+1];
int vstt[MAX_N+1];
vector<int> v;

void dfs(int x){
	v.pb(x);
	vstt[x] = 1;
	sz2[x] = 1;
	dfsn[x] = up[x] = ++cnt;
	for(int i : gp[x]){
		if(i==p[x])	continue;
		if(dfsn[i]==0){
			p[i] = x;
			dfs(i);
			sz2[x]+=sz2[i];
			up[x] = min(up[x], up[i]);
		}else{
			up[x] = min(up[x], dfsn[i]);
		}
	}
}

vector<int> BCC[MAX_N+1];
vector<int> cl[MAX_N+1];
vector<pii> sz[MAX_N+1];
bool vst[MAX_N+1];
int sz3[MAX_N+1];
vector<pii> sz4[MAX_N+1];

void color(int x, int y){
	if(y>0){
		BCC[y].pb(x);
		cl[x].pb(y);
	}
	vst[x] = true;
	bool tf = false;
	int sum = 0;
	for(int i : gp[x]){
		if(vst[i])	continue;
		if(dfsn[x]<=up[i]){
			tf = true;
			BCC[++cnt].pb(x);
			if(N-sz2[i]-1!=0)	{
				sz[cnt].pb({x, N - sz2[i] - 1});
				sz4[x].pb({cnt, sz2[i]});
			}
			sum += sz2[i];
			cl[x].pb(cnt);
			color(i, cnt);
		}else{
			color(i, y);
		}
	}
	if(tf && y>0){
		sz[y].pb({x, sum});
		sz4[x].pb({y, N - 1 - sum});
	}
}

ll ans;
ll calc[MAX_N+1];


int main(){
	scanf("%d%d", &NN, &M);
	for(int i=1; i<=M; i++){
		int a, b; scanf("%d%d", &a, &b);
		gp[a].pb(b); gp[b].pb(a);
	}
	for(int i=1; i<=NN; i++){
		if(vstt[i]) continue;
		while(!v.empty())	v.pop_back();
		dfs(i); 
		N = v.size();
		cnt = 0; color(i, 0);
		for(int i:v){
			calc[i] = 1;
			for(int j : cl[i]){
				sz3[i] += (BCC[j].size() - 1);
			}
			TEST cout<<i<<" "<<sz3[i]<<endl;
			ans += (ll)sz3[i] * (ll)(sz3[i]-1);
		}
		for(int i=pcnt; i<=cnt; i++){
			// type 2
			ll sum1 = 0, sum2 = 0;
			ll num = 0;
			TEST cout<<i<<endl;
			for(int j : BCC[i]){
				TEST cout<<j<<" ";
				if(cl[j].size()==1)	num++;
			}
			TEST cout<<endl;
			TEST cout<<num<<endl;
			ans += num * (num-1) * (ll)(N - BCC[i].size()) * 2LL;
			for(pii j : sz[i]){
				sum2 += sum1 * (ll)j.second;
				sum1 += (ll)j.second;
				ans += 2LL * num * (ll)(N - BCC[i].size() - j.second);
				TEST cout<<j.first<<" "<<j.second<<endl;
				TEST cout<<"*"<<(N-BCC[i].size() -j.second)<<endl;
				ans += 2LL * (ll)(BCC[i].size()-1) * (ll)(j.second - sz3[j.first] + BCC[i].size() - 1);
				TEST cout<<"&"<<(j.second - sz3[j.first] + BCC[i].size() - 1)<<endl;
			}
			TEST cout<<num<<" "<<sum2<<endl;
			ans += num * 2LL * sum2;
		}
		TEST cout<<ans<<endl;
		for(int i : v){
			if(cl[i].size()>1){
				ll sum1 = 0, sum2 = 0;
				TEST cout<<i<<endl;
				for(pii j : sz4[i]){
					TEST cout<<j.first<<" "<<j.second<<endl;
					sum2 += (ll)(j.second - BCC[j.first].size() + 1) * sum1;
					sum1 += (ll)(j.second - BCC[j.first].size() + 1);
				}
				ans += 2LL * sum2;
			}
		}
		pcnt = cnt;
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &NN, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12024 KB Output is correct
2 Correct 12 ms 12280 KB Output is correct
3 Correct 12 ms 12152 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 15 ms 12024 KB Output is correct
6 Correct 15 ms 12024 KB Output is correct
7 Incorrect 14 ms 12152 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12024 KB Output is correct
2 Correct 12 ms 12280 KB Output is correct
3 Correct 12 ms 12152 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 15 ms 12024 KB Output is correct
6 Correct 15 ms 12024 KB Output is correct
7 Incorrect 14 ms 12152 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 33048 KB Output is correct
2 Correct 145 ms 33040 KB Output is correct
3 Incorrect 187 ms 32388 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12280 KB Output is correct
2 Correct 13 ms 12280 KB Output is correct
3 Correct 13 ms 12280 KB Output is correct
4 Correct 13 ms 12408 KB Output is correct
5 Correct 13 ms 12412 KB Output is correct
6 Correct 13 ms 12280 KB Output is correct
7 Correct 13 ms 12408 KB Output is correct
8 Correct 14 ms 12360 KB Output is correct
9 Correct 13 ms 12408 KB Output is correct
10 Incorrect 13 ms 12280 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 31816 KB Output is correct
2 Correct 190 ms 31920 KB Output is correct
3 Correct 271 ms 31860 KB Output is correct
4 Correct 187 ms 31972 KB Output is correct
5 Correct 189 ms 31832 KB Output is correct
6 Correct 218 ms 37684 KB Output is correct
7 Correct 245 ms 35624 KB Output is correct
8 Correct 226 ms 34676 KB Output is correct
9 Correct 230 ms 33724 KB Output is correct
10 Incorrect 190 ms 29560 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 31844 KB Output is correct
2 Correct 199 ms 32012 KB Output is correct
3 Incorrect 197 ms 31072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12024 KB Output is correct
2 Correct 12 ms 12280 KB Output is correct
3 Correct 12 ms 12152 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 15 ms 12024 KB Output is correct
6 Correct 15 ms 12024 KB Output is correct
7 Incorrect 14 ms 12152 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12024 KB Output is correct
2 Correct 12 ms 12280 KB Output is correct
3 Correct 12 ms 12152 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 15 ms 12024 KB Output is correct
6 Correct 15 ms 12024 KB Output is correct
7 Incorrect 14 ms 12152 KB Output isn't correct
8 Halted 0 ms 0 KB -