oj.uz

Submission #172214

# Submission time Handle Problem Language Result Execution time Memory
172214 2019-12-31T16:24:55 Z dndhk Duathlon (APIO18_duathlon) C++14
31 / 100
 256 ms 37108 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;


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 = pcnt-1; color(i, 0);
		for(int i:v){
			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-1LL) * (ll)(N - BCC[i].size()) * 2LL;
			for(pii j : sz[i]){
				sum2 += sum1 * (ll)j.second;
				sum1 += (ll)j.second;
				ans += 2LL * (ll)(BCC[i].size() - num - 1) * (ll)(N - j.second - sz3[j.first] - 1);
				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 * num * (ll)(N - sz3[j.first] - 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+1;
		cnt = 0;
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:93: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:95: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 12152 KB Output is correct
2 Correct 12 ms 12152 KB Output is correct
3 Correct 12 ms 12152 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 12 ms 12152 KB Output is correct
6 Correct 13 ms 12152 KB Output is correct
7 Incorrect 13 ms 12024 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 12152 KB Output is correct
2 Correct 12 ms 12152 KB Output is correct
3 Correct 12 ms 12152 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 12 ms 12152 KB Output is correct
6 Correct 13 ms 12152 KB Output is correct
7 Incorrect 13 ms 12024 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 32296 KB Output is correct
2 Correct 154 ms 32284 KB Output is correct
3 Correct 193 ms 31728 KB Output is correct
4 Correct 173 ms 32232 KB Output is correct
5 Correct 166 ms 28664 KB Output is correct
6 Correct 217 ms 30828 KB Output is correct
7 Correct 185 ms 29820 KB Output is correct
8 Correct 205 ms 30664 KB Output is correct
9 Correct 190 ms 28888 KB Output is correct
10 Correct 187 ms 28792 KB Output is correct
11 Correct 138 ms 25268 KB Output is correct
12 Correct 135 ms 25160 KB Output is correct
13 Correct 126 ms 24412 KB Output is correct
14 Correct 127 ms 24288 KB Output is correct
15 Correct 128 ms 22428 KB Output is correct
16 Correct 124 ms 22264 KB Output is correct
17 Correct 18 ms 14456 KB Output is correct
18 Correct 18 ms 14456 KB Output is correct
19 Correct 19 ms 14404 KB Output is correct
20 Correct 18 ms 14328 KB Output is correct
21 Correct 18 ms 14328 KB Output is correct
22 Correct 21 ms 14328 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 31020 KB Output is correct
2 Correct 201 ms 31216 KB Output is correct
3 Correct 205 ms 31092 KB Output is correct
4 Correct 217 ms 31092 KB Output is correct
5 Correct 211 ms 31092 KB Output is correct
6 Correct 241 ms 37108 KB Output is correct
7 Correct 256 ms 34904 KB Output is correct
8 Correct 244 ms 33908 KB Output is correct
9 Correct 229 ms 33012 KB Output is correct
10 Correct 218 ms 30968 KB Output is correct
11 Correct 208 ms 31224 KB Output is correct
12 Correct 218 ms 30840 KB Output is correct
13 Correct 210 ms 30712 KB Output is correct
14 Correct 168 ms 29516 KB Output is correct
15 Correct 157 ms 28116 KB Output is correct
16 Correct 99 ms 23244 KB Output is correct
17 Correct 137 ms 30316 KB Output is correct
18 Correct 146 ms 30292 KB Output is correct
19 Correct 142 ms 30768 KB Output is correct
20 Correct 160 ms 30308 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 30956 KB Output is correct
2 Correct 216 ms 31124 KB Output is correct
3 Incorrect 215 ms 29804 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 12152 KB Output is correct
2 Correct 12 ms 12152 KB Output is correct
3 Correct 12 ms 12152 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 12 ms 12152 KB Output is correct
6 Correct 13 ms 12152 KB Output is correct
7 Incorrect 13 ms 12024 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 12152 KB Output is correct
2 Correct 12 ms 12152 KB Output is correct
3 Correct 12 ms 12152 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 12 ms 12152 KB Output is correct
6 Correct 13 ms 12152 KB Output is correct
7 Incorrect 13 ms 12024 KB Output isn't correct
8 Halted 0 ms 0 KB -