oj.uz

Submission #106480

# Submission time Handle Problem Language Result Execution time Memory
106480 2019-04-18T18:54:01 Z Frankenween Shymbulak (IZhO14_shymbulak) C++17
30 / 100
 1500 ms 263168 KB 
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#define ull unsigned long long
#define pll pair<ll, ll>
#define mp make_pair
#define ll long long
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define ld long double
const ll mod = (ll)1e9 + 7;
const ll BASE = 47;
const ll inf = (ll)1e18;
const long double e = 2.718281828459;
const long double pi = 3.141592653;
const ld EPS = 1e-9;


using namespace std;


template <class T>
istream& operator>>(istream &in, vector<T> &arr) {
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};


void solve() {
    ll n;
    cin >> n;
    vector<vector<pair<ll, ll>>> g(n, vector<pair<ll, ll>>(n, {inf, 0}));
    for (int i = 0; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a][b] = {1, 1};
        g[b][a] = {1, 1};
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j].first > g[i][k].first + g[k][j].first) {
                    g[i][j].first = g[i][k].first + g[k][j].first;
                    g[i][j].second = g[i][k].second * g[k][j].second;
                } else if (g[i][j].first == g[i][k].first + g[k][j].first) {
                    g[i][j].second += g[i][k].second * g[k][j].second;
                }
            }
        }
    }
    vector<ll> answer(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            answer[g[i][j].first] += g[i][j].second;
        }
    }
    while (answer.back() == 0) {
        answer.pop_back();
    }
    cout << answer.back();
}


int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#else
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout.precision(30);
    ll seed = time(0);
    //cerr << "Seed: " << seed << "\n";
    srand(seed);
    solve();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 300 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 388 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 10 ms 768 KB Output is correct
14 Correct 171 ms 4352 KB Output is correct
15 Correct 150 ms 4224 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 8064 KB Output is correct
2 Correct 865 ms 10368 KB Output is correct
3 Execution timed out 1563 ms 16128 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 180 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -