oj.uz

답안 #758212

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758212 2023-06-14T09:27:46 Z vjudge1 Hard route (IZhO17_road) C++17
19 / 100
 2000 ms 720 KB 
#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 1000007
#define INF 1000000000000000000
//#define ll long long
///#define cin fin
///#define cout fout
#define fi first
#define se second
using namespace std;
double const EPS = 1e-14;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
const int Max = 5000 + 5;
vector<int> v[Max];
bool mark[Max], mark2[Max]; vector<int> ter, order;
int start; int path, path2, path3, path4;
pair<int,int> ans;

void dfs2(int s, int p) {
    path2 = max(path2,path3);
    for(auto i : v[s]) {
        if(i != p && mark2[i] == 0) {
            path3++;
            dfs2(i,s);
            path3--;
        }
    }
}

void dfs(int s, int p) {
    order.push_back(s);
    mark2[s] = 1;
    if(mark[s] == 1 && s != start) {
        path4 = 0;
        for(int i = 0; i < order.size(); i++) {
            path2 = 0;
            dfs2(order[i],0);
            path4 = max(path4,path2);

        }
        if(ans.first < path*path4) {
            ans.first = path*path4;
            ans.second = 1;
        } else if(ans.first == path*path4) {
            ans.second++;
        }
    }
    for(auto i : v[s]) {
        if(i != p) {
            path++;
            dfs(i,s);
            path--;
        }
    }
    order.pop_back();
    mark2[s] = 0;
}

int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n; cin >> n; ans.second = 1;
    for(int i = 0; i < n-1 ; i++) {
        int a, b; cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) {
        if(v[i].size() == 1) {
            mark[i] = 1;
            ter.push_back(i);
        }
    }
    for(int i = 0; i < ter.size(); i++) {
        start = ter[i];
        dfs(ter[i],0);
    }
    cout << ans.first << ' ' << ans.second/2;
 return 0;
}

Compilation message

road.cpp: In function 'void dfs(int, int)':
road.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int i = 0; i < order.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~
road.cpp: In function 'int main()':
road.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < ter.size(); i++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
19.0 / 19.0

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

Subtask #2
0 / 33.0

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

Subtask #3
0 / 48.0

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