oj.uz

답안 #957707

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957707 2024-04-04T08:33:15 Z noobcodur Hard route (IZhO17_road) C++14
0 / 100
 2 ms 7004 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define forn(i,j) for(int i = 0; i < j; i++)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define pb push_back
#define s second
#define all(x) x.begin(),x.end()

const int MOD = 1e9 + 7; const int INF = 1e17 + 1; const int maxN = 2e5 + 1;

void setIO(string name = ""){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	if(!name.empty()){
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

struct Node{
	int d1 = 0, d2 = 0, d3 = 0;

	void add(int a){
		if(d1 < a){
			int curr_d1 = d1; int curr_d2 = d2;
			d1 = a; d2 = curr_d1; d3 = curr_d2;
			return;
		}

		if(d2 < a){
			int curr_d2 = d2;
			d2 = a; d3 = curr_d2;
			return;
		}

		d3 = max(d3,a);
	}
};

vi graph[maxN]; Node vtx[maxN];
int subtree_dist[maxN];

void dfs(int src, int prev){
	subtree_dist[src] = 0;

	for(int ch : graph[src]){
		if(ch == prev) continue;
		dfs(ch,src);

		subtree_dist[src] = max(subtree_dist[src],subtree_dist[ch]+1);
		vtx[src].add(subtree_dist[ch]+1);
	}
} 

void dfs2(int src, int prev){
	for(int ch : graph[src]){
		if(ch == prev) continue;
		if(subtree_dist[ch]+1 == vtx[src].d1){
			vtx[ch].add(vtx[src].d2+1);
		}

		else{
			vtx[ch].add(vtx[src].d1+1);
		}

		dfs2(ch,src);
	}
}

signed main(){
	setIO();
	int n; cin >> n;

	forn(i,n-1){
		int a,b; cin >> a >> b;
		graph[a].pb(b); graph[b].pb(a);
	}

	dfs(1,-1); dfs2(1,-1);
	int ans = 0;

	forrange(i,1,n+1){
		if(vtx[i].d3 == 0) continue;
		ans = max(ans,vtx[i].d1*(vtx[i].d2+vtx[i].d3));
	}

	int freq = 0;

	if(ans == 0){
		cout << ans << " " << 1 << endl;
		return 0;
	}

	forrange(i,1,n+1){
		if(vtx[i].d1*(vtx[i].d2+vtx[i].d3) == ans){
			if(vtx[i].d1 == vtx[i].d2 && vtx[i].d3 != vtx[i].d1){
				freq += 2; continue;
			}

			else if(vtx[i].d1 == vtx[i].d2 == vtx[i].d3){
				freq += 3; continue;
			}

			freq++;
		}
	}

	cout << ans << " " << freq << endl;
}

Compilation message

road.cpp: In function 'int main()':
road.cpp:107:22: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
  107 |    else if(vtx[i].d1 == vtx[i].d2 == vtx[i].d3){
      |            ~~~~~~~~~~^~~~~~~~~~~~
road.cpp: In function 'void setIO(std::string)':
road.cpp:22:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road.cpp:23:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Incorrect 2 ms 7004 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Incorrect 2 ms 7004 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Incorrect 2 ms 7004 KB Output isn't correct
8 Halted 0 ms 0 KB -