oj.uz

Submission #172197

# Submission time Handle Problem Language Result Execution time Memory
172197 2019-12-31T14:48:45 Z dndhk Duathlon (APIO18_duathlon) C++14
31 / 100
 233 ms 36420 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 = pcnt-1; 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+1;
		cnt = 0;
	}
	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 14 ms 12024 KB Output is correct
3 Correct 15 ms 12024 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 12 ms 12028 KB Output is correct
6 Correct 12 ms 12152 KB Output is correct
7 Incorrect 12 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 12024 KB Output is correct
2 Correct 14 ms 12024 KB Output is correct
3 Correct 15 ms 12024 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 12 ms 12028 KB Output is correct
6 Correct 12 ms 12152 KB Output is correct
7 Incorrect 12 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 136 ms 31912 KB Output is correct
2 Correct 148 ms 31744 KB Output is correct
3 Correct 188 ms 31280 KB Output is correct
4 Correct 164 ms 32848 KB Output is correct
5 Correct 169 ms 29528 KB Output is correct
6 Correct 200 ms 31600 KB Output is correct
7 Correct 205 ms 30576 KB Output is correct
8 Correct 198 ms 31348 KB Output is correct
9 Correct 177 ms 29652 KB Output is correct
10 Correct 176 ms 29620 KB Output is correct
11 Correct 127 ms 26084 KB Output is correct
12 Correct 125 ms 25976 KB Output is correct
13 Correct 117 ms 25336 KB Output is correct
14 Correct 113 ms 25208 KB Output is correct
15 Correct 90 ms 23252 KB Output is correct
16 Correct 89 ms 23080 KB Output is correct
17 Correct 18 ms 15224 KB Output is correct
18 Correct 18 ms 15224 KB Output is correct
19 Correct 18 ms 15224 KB Output is correct
20 Correct 18 ms 15224 KB Output is correct
21 Correct 18 ms 15096 KB Output is correct
22 Correct 18 ms 15096 KB Output is correct

Subtask #4
10.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 15 ms 12324 KB Output is correct
4 Correct 14 ms 12296 KB Output is correct
5 Correct 14 ms 12284 KB Output is correct
6 Correct 13 ms 12280 KB Output is correct
7 Correct 16 ms 12280 KB Output is correct
8 Correct 13 ms 12280 KB Output is correct
9 Correct 13 ms 12280 KB Output is correct
10 Correct 13 ms 12280 KB Output is correct
11 Correct 14 ms 12280 KB Output is correct
12 Correct 16 ms 12280 KB Output is correct
13 Correct 13 ms 12280 KB Output is correct
14 Correct 15 ms 12280 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 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 183 ms 30584 KB Output is correct
2 Correct 178 ms 30580 KB Output is correct
3 Correct 177 ms 30580 KB Output is correct
4 Correct 180 ms 30724 KB Output is correct
5 Correct 195 ms 30704 KB Output is correct
6 Correct 233 ms 36420 KB Output is correct
7 Correct 220 ms 34360 KB Output is correct
8 Correct 207 ms 33400 KB Output is correct
9 Correct 231 ms 32404 KB Output is correct
10 Correct 210 ms 30540 KB Output is correct
11 Correct 199 ms 31828 KB Output is correct
12 Correct 200 ms 31608 KB Output is correct
13 Correct 205 ms 31548 KB Output is correct
14 Correct 158 ms 30208 KB Output is correct
15 Correct 146 ms 28840 KB Output is correct
16 Correct 91 ms 24044 KB Output is correct
17 Correct 127 ms 31244 KB Output is correct
18 Correct 128 ms 31208 KB Output is correct
19 Correct 139 ms 31588 KB Output is correct
20 Correct 134 ms 31116 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12284 KB Output is correct
2 Correct 13 ms 12280 KB Output is correct
3 Incorrect 13 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 193 ms 30692 KB Output is correct
2 Correct 206 ms 30728 KB Output is correct
3 Incorrect 207 ms 29424 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 14 ms 12024 KB Output is correct
3 Correct 15 ms 12024 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 12 ms 12028 KB Output is correct
6 Correct 12 ms 12152 KB Output is correct
7 Incorrect 12 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 12024 KB Output is correct
2 Correct 14 ms 12024 KB Output is correct
3 Correct 15 ms 12024 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 12 ms 12028 KB Output is correct
6 Correct 12 ms 12152 KB Output is correct
7 Incorrect 12 ms 12024 KB Output isn't correct
8 Halted 0 ms 0 KB -