oj.uz

Submission #172210

# Submission time Handle Problem Language Result Execution time Memory
172210 2019-12-31T15:17:11 Z dndhk Duathlon (APIO18_duathlon) C++14
31 / 100
 262 ms 36980 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-1) * (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 * (ll)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)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 13 ms 12024 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 12 ms 12152 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 13 ms 12152 KB Output is correct
7 Incorrect 13 ms 12144 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12024 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 12 ms 12152 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 13 ms 12152 KB Output is correct
7 Incorrect 13 ms 12144 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 141 ms 31628 KB Output is correct
2 Correct 143 ms 31568 KB Output is correct
3 Correct 204 ms 31184 KB Output is correct
4 Correct 195 ms 32100 KB Output is correct
5 Correct 180 ms 28660 KB Output is correct
6 Correct 215 ms 30780 KB Output is correct
7 Correct 215 ms 30044 KB Output is correct
8 Correct 213 ms 30580 KB Output is correct
9 Correct 184 ms 28792 KB Output is correct
10 Correct 203 ms 28812 KB Output is correct
11 Correct 156 ms 25348 KB Output is correct
12 Correct 181 ms 25040 KB Output is correct
13 Correct 132 ms 24508 KB Output is correct
14 Correct 117 ms 24184 KB Output is correct
15 Correct 94 ms 22336 KB Output is correct
16 Correct 97 ms 22288 KB Output is correct
17 Correct 19 ms 14460 KB Output is correct
18 Correct 18 ms 14456 KB Output is correct
19 Correct 18 ms 14456 KB Output is correct
20 Correct 18 ms 14332 KB Output is correct
21 Correct 18 ms 14328 KB Output is correct
22 Correct 18 ms 14328 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12280 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 14 ms 12280 KB Output is correct
4 Correct 14 ms 12280 KB Output is correct
5 Correct 14 ms 12280 KB Output is correct
6 Correct 14 ms 12328 KB Output is correct
7 Correct 14 ms 12280 KB Output is correct
8 Correct 14 ms 12284 KB Output is correct
9 Correct 14 ms 12280 KB Output is correct
10 Correct 14 ms 12280 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 12280 KB Output is correct
14 Correct 14 ms 12280 KB Output is correct
15 Correct 15 ms 12280 KB Output is correct
16 Correct 13 ms 12152 KB Output is correct
17 Correct 14 ms 12280 KB Output is correct
18 Correct 13 ms 12280 KB Output is correct
19 Correct 14 ms 12200 KB Output is correct
20 Correct 14 ms 12280 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 30468 KB Output is correct
2 Correct 205 ms 31092 KB Output is correct
3 Correct 205 ms 31128 KB Output is correct
4 Correct 207 ms 31092 KB Output is correct
5 Correct 187 ms 31092 KB Output is correct
6 Correct 262 ms 36980 KB Output is correct
7 Correct 215 ms 34804 KB Output is correct
8 Correct 228 ms 33896 KB Output is correct
9 Correct 250 ms 33016 KB Output is correct
10 Correct 199 ms 30972 KB Output is correct
11 Correct 196 ms 31008 KB Output is correct
12 Correct 207 ms 30820 KB Output is correct
13 Correct 210 ms 30780 KB Output is correct
14 Correct 158 ms 29432 KB Output is correct
15 Correct 140 ms 28024 KB Output is correct
16 Correct 118 ms 23332 KB Output is correct
17 Correct 142 ms 30444 KB Output is correct
18 Correct 134 ms 30436 KB Output is correct
19 Correct 134 ms 30692 KB Output is correct
20 Correct 141 ms 30320 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12280 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Incorrect 15 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 214 ms 30872 KB Output is correct
2 Correct 207 ms 31344 KB Output is correct
3 Incorrect 207 ms 30108 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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