답안 #1118424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118424	2024-11-25T13:31:44 Z	Younis_Dwai	Hard route (IZhO17_road)	C++14	19 / 100	2000 ms	848 KB

road

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define int long long
#define in insert
#define mid (l+r)/2
#define in insert
using namespace std;
const int N=5e3+5;
int n,depth[N],p[N],dis[N],mx=0,ret=0;
vector<int> adj[N];
void dfs(int node , int par){
     p[node]=par;
     for(auto u : adj[node]){
         if(u==par) continue ;
         depth[u]=1+depth[node];
         dfs(u,node);
     }
     return ;
}
void calc(int u , int v){
     for(int i=1;i<=n;i++) dis[i]=1e5;
     queue<int> q;
     dis[v]=dis[u]=0;
     q.push(v);
     int ct=0;
     while(v!=u){
           v=p[v];
           dis[v]=0;
           q.push(v);
           ++ct;
     }
     while(!q.empty()){
           int node=q.front();
           q.pop();
           for(auto u : adj[node]){
               if(dis[u]>1+dis[node]){
                  dis[u]=1+dis[node];
                  q.push(u);
               }
           }
     }
     int bb=0;
     for(int i=1;i<=n;i++){
         bb=max(bb,dis[i]);
     }
     if(ct*bb==mx) ret++;
     else if(ct*bb>mx){
           ret=1;
           mx=ct*bb;
     }
     return ;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(adj[i].size()!=1 || adj[j].size()!=1) continue ;
            depth[i]=0;
            dfs(i,i);
            calc(i,j);
        }
    }
    cout<<mx<<' '<<ret;
    return 0;
}

Subtask #1

19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	592 KB	Output is correct
2	Correct	1 ms	592 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	588 KB	Output is correct
5	Correct	1 ms	580 KB	Output is correct
6	Correct	1 ms	588 KB	Output is correct
7	Correct	2 ms	592 KB	Output is correct
8	Correct	2 ms	592 KB	Output is correct
9	Correct	1 ms	592 KB	Output is correct
10	Correct	2 ms	592 KB	Output is correct
11	Correct	2 ms	592 KB	Output is correct
12	Correct	2 ms	592 KB	Output is correct
13	Correct	3 ms	336 KB	Output is correct
14	Correct	2 ms	592 KB	Output is correct
15	Correct	1 ms	592 KB	Output is correct
16	Correct	2 ms	592 KB	Output is correct
17	Correct	1 ms	592 KB	Output is correct
18	Correct	1 ms	592 KB	Output is correct
19	Correct	1 ms	592 KB	Output is correct
20	Correct	1 ms	760 KB	Output is correct
21	Correct	1 ms	592 KB	Output is correct
22	Correct	1 ms	592 KB	Output is correct
23	Correct	1 ms	592 KB	Output is correct
24	Correct	5 ms	596 KB	Output is correct

Subtask #2

0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	592 KB	Output is correct
2	Correct	1 ms	592 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	588 KB	Output is correct
5	Correct	1 ms	580 KB	Output is correct
6	Correct	1 ms	588 KB	Output is correct
7	Correct	2 ms	592 KB	Output is correct
8	Correct	2 ms	592 KB	Output is correct
9	Correct	1 ms	592 KB	Output is correct
10	Correct	2 ms	592 KB	Output is correct
11	Correct	2 ms	592 KB	Output is correct
12	Correct	2 ms	592 KB	Output is correct
13	Correct	3 ms	336 KB	Output is correct
14	Correct	2 ms	592 KB	Output is correct
15	Correct	1 ms	592 KB	Output is correct
16	Correct	2 ms	592 KB	Output is correct
17	Correct	1 ms	592 KB	Output is correct
18	Correct	1 ms	592 KB	Output is correct
19	Correct	1 ms	592 KB	Output is correct
20	Correct	1 ms	760 KB	Output is correct
21	Correct	1 ms	592 KB	Output is correct
22	Correct	1 ms	592 KB	Output is correct
23	Correct	1 ms	592 KB	Output is correct
24	Correct	5 ms	596 KB	Output is correct
25	Execution timed out	2054 ms	848 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

Subtask #3

0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	592 KB	Output is correct
2	Correct	1 ms	592 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	588 KB	Output is correct
5	Correct	1 ms	580 KB	Output is correct
6	Correct	1 ms	588 KB	Output is correct
7	Correct	2 ms	592 KB	Output is correct
8	Correct	2 ms	592 KB	Output is correct
9	Correct	1 ms	592 KB	Output is correct
10	Correct	2 ms	592 KB	Output is correct
11	Correct	2 ms	592 KB	Output is correct
12	Correct	2 ms	592 KB	Output is correct
13	Correct	3 ms	336 KB	Output is correct
14	Correct	2 ms	592 KB	Output is correct
15	Correct	1 ms	592 KB	Output is correct
16	Correct	2 ms	592 KB	Output is correct
17	Correct	1 ms	592 KB	Output is correct
18	Correct	1 ms	592 KB	Output is correct
19	Correct	1 ms	592 KB	Output is correct
20	Correct	1 ms	760 KB	Output is correct
21	Correct	1 ms	592 KB	Output is correct
22	Correct	1 ms	592 KB	Output is correct
23	Correct	1 ms	592 KB	Output is correct
24	Correct	5 ms	596 KB	Output is correct
25	Execution timed out	2054 ms	848 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-