oj.uz

Submission #111213

# Submission time Handle Problem Language Result Execution time Memory
111213 2019-05-14T08:23:40 Z Just_Solve_The_Problem Duathlon (APIO18_duathlon) C++11
0 / 100
 206 ms 27088 KB 
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)2e5 + 7;

int tin[N], fup[N], sz[N];
int tiktak;
vector <int> gr[N];
vector <int> ngr[N];
int n, m, cl, mm;
stack<int> st;
ll ans = 0;

void dfs(int v, int pr) {
	tin[v] = fup[v] = ++tiktak;
	st.push(v);
	mm++;
	for (int to : gr[v]) {
		if (to == pr) continue;
		if (!tin[to]) {
			dfs(to, v);
			fup[v] = min(fup[v], fup[to]);
			if (fup[to] >= tin[v]) {
				cl++;
				ngr[v].push_back(n + cl);
				while (ngr[n + cl].empty() || ngr[n + cl].back() != to) {
					ngr[n + cl].push_back(st.top());
					st.pop();
				}
			}
		} else {
			fup[v] = min(fup[v], tin[to]);
		}
	}
}

void dfs1(int v) {
	sz[v] = (v <= n);
	for (int to : ngr[v]) {
		dfs1(to);
		sz[v] += sz[to];
		if (v > n)
			ans -= (ngr[v].size() * 1LL * (sz[to] - 1) * sz[to]);
	}
	if (v > n) 
		ans -= ngr[v].size() * 1LL * (mm - sz[v]) * (mm - sz[v] - 1);
}

main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		gr[u].push_back(v);
		gr[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		if (!tin[i]) {
			mm = 0;
			dfs(i, i);
			cerr << mm << endl;
			ans += mm * 1LL * (mm - 1) * (mm - 2);
			dfs1(i);
		}
	}
	cout << ans;
}

Compilation message

count_triplets.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 27088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 20600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 20572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -