oj.uz

Submission #273623

# Submission time Handle Problem Language Result Execution time Memory
273623 2020-08-19T06:11:49 Z 임성재(#5106) Mountains and Valleys (CCO20_day1problem3) C++17
2 / 25
 5 ms 640 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
vector<int> g[5010];

pii f(int r) {
	queue<int> q;
	int d[5010] = {};

	d[r] = 1;
	q.em(r);

	while(q.size()) {
		int x = q.front();
		q.pop();

		for(auto i : g[x]) {
			if(d[i]) continue;

			d[i] = d[x] +  1;
			q.em(i);
		}
	}

	int mx = -1, mxi;
	for(int i=1; i<=n; i++) {
		if(d[i]-1 > mx) {
			mx = d[i] - 1;
			mxi = i;
		}
	}

	return mp(mx, mxi);
}

int main() {
	fast;

	cin >> n >> m;

	for(int i=0; i<m; i++) {
		int x, y, w;
		cin >> x >> y >> w;

		if(w == 1) {
			g[x].eb(y);
			g[y].eb(x);
		}
	}

	int D = f(f(0).se).fi;

	cout << 2 * n - 2 - D;
}

Compilation message

Main.cpp: In function 'pii f(int)':
Main.cpp:40:15: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |  int mx = -1, mxi;
      |               ^~~

Subtask #1
0.0 / 1.0

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

Subtask #2
0.0 / 2.0

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

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct

Subtask #4
0.0 / 6.0

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

Subtask #5
0.0 / 2.0

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

Subtask #6
0.0 / 3.0

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

Subtask #7
0.0 / 5.0

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

Subtask #8
0.0 / 4.0

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