제출 #957707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
957707		noobcodur	Hard route (IZhO17_road)	C++14	0 / 100	2 ms	7004 KiB

road

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48