oj.uz

Submission #172199

# Submission time Handle Problem Language Result Execution time Memory
172199 2019-12-31T14:51:18 Z dndhk Duathlon (APIO18_duathlon) C++14
31 / 100
 276 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 * 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 * 4LL * 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 13 ms 12024 KB Output is correct
4 Correct 13 ms 12024 KB Output is correct
5 Correct 13 ms 12024 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 13 ms 12024 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 13 ms 12024 KB Output is correct
4 Correct 13 ms 12024 KB Output is correct
5 Correct 13 ms 12024 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 153 ms 32248 KB Output is correct
2 Correct 143 ms 32160 KB Output is correct
3 Correct 192 ms 31700 KB Output is correct
4 Correct 165 ms 32056 KB Output is correct
5 Correct 161 ms 28700 KB Output is correct
6 Correct 190 ms 30708 KB Output is correct
7 Correct 202 ms 29816 KB Output is correct
8 Correct 196 ms 30620 KB Output is correct
9 Correct 200 ms 28884 KB Output is correct
10 Correct 192 ms 28740 KB Output is correct
11 Correct 126 ms 25336 KB Output is correct
12 Correct 128 ms 25080 KB Output is correct
13 Correct 118 ms 24500 KB Output is correct
14 Correct 116 ms 24184 KB Output is correct
15 Correct 89 ms 22328 KB Output is correct
16 Correct 87 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 18 ms 14456 KB Output is correct
20 Correct 17 ms 14456 KB Output is correct
21 Correct 21 ms 14332 KB Output is correct
22 Correct 18 ms 14456 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 13 ms 12280 KB Output is correct
3 Correct 14 ms 12280 KB Output is correct
4 Correct 17 ms 12280 KB Output is correct
5 Correct 14 ms 12280 KB Output is correct
6 Correct 14 ms 12408 KB Output is correct
7 Correct 21 ms 12408 KB Output is correct
8 Correct 16 ms 12280 KB Output is correct
9 Correct 14 ms 12280 KB Output is correct
10 Correct 13 ms 12280 KB Output is correct
11 Correct 16 ms 12244 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 12284 KB Output is correct
15 Correct 13 ms 12280 KB Output is correct
16 Correct 13 ms 12280 KB Output is correct
17 Correct 13 ms 12280 KB Output is correct
18 Correct 13 ms 12280 KB Output is correct
19 Correct 14 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 188 ms 31028 KB Output is correct
2 Correct 191 ms 31100 KB Output is correct
3 Correct 218 ms 31228 KB Output is correct
4 Correct 197 ms 31228 KB Output is correct
5 Correct 227 ms 31200 KB Output is correct
6 Correct 237 ms 36980 KB Output is correct
7 Correct 216 ms 34808 KB Output is correct
8 Correct 211 ms 34016 KB Output is correct
9 Correct 218 ms 32984 KB Output is correct
10 Correct 194 ms 30840 KB Output is correct
11 Correct 198 ms 30964 KB Output is correct
12 Correct 212 ms 30788 KB Output is correct
13 Correct 206 ms 30712 KB Output is correct
14 Correct 155 ms 29372 KB Output is correct
15 Correct 152 ms 28008 KB Output is correct
16 Correct 92 ms 23308 KB Output is correct
17 Correct 134 ms 30312 KB Output is correct
18 Correct 133 ms 30316 KB Output is correct
19 Correct 142 ms 30792 KB Output is correct
20 Correct 138 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 13 ms 12252 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 201 ms 31064 KB Output is correct
2 Correct 276 ms 31260 KB Output is correct
3 Incorrect 218 ms 30296 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 13 ms 12024 KB Output is correct
4 Correct 13 ms 12024 KB Output is correct
5 Correct 13 ms 12024 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 13 ms 12024 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 13 ms 12024 KB Output is correct
4 Correct 13 ms 12024 KB Output is correct
5 Correct 13 ms 12024 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 -