oj.uz

답안 #125713

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125713 2019-07-06T09:16:29 Z srvlt 관광지 (IZhO14_shymbulak) C++14
0 / 100
 106 ms 55800 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
using namespace std;

const int N = 5002;
int n, X, Y, X2, Y2, parent[N], sz[N], d[N][N], d1[N][N], d2[N][N], ans;
bool used[N][N], used1[N][N], used2[N][N], c[N][N];
pair <int, int> ed[N];
vector <int> q[N];

void make_set(int x) {
    parent[x] = x;
    sz[x] = 1;
}

int find_set(int x) {
    if (x == parent[x])
        return x;
    return parent[x] = find_set(parent[x]);
}

void union_set(int x, int y) {
    x = find_set(x);
    y = find_set(y);
    if (x != y) {
        if (sz[x] < sz[y])
            swap(x, y);
        parent[y] = x;
        sz[x] += sz[y];
    }
}

void bfs(int v) {
    queue <int> t;
    t.push(v);
    used[v][v] = true;
    while (!t.empty()) {
        int z = t.front();
        t.pop();
        for (auto i : q[z]) {
            if (used[v][i])
                continue;
            used[v][i] = true;
            d[v][i] = d[v][z] + 1;
            t.push(i);
        }
    }
}

void bfs1(int v) {
    queue <int> t;
    t.push(v);
    used1[v][v] = true;
    while (!t.empty()) {
        int z = t.front();
        t.pop();
        for (auto i : q[z]) {
            if (used1[v][i])
                continue;
            c[v][i] = c[v][z];
            if ((z == X && i == Y) || (z == Y && i == X)) {
                c[v][i] = true;
            }
            used1[v][i] = true;
            d1[v][i] = d1[v][z] + 1;
            t.push(i);
        }
    }
}

void del(int x, int y) {
    for (int i = 0; i < q[x].size(); i++) {
        if (q[x][i] == y) {
            q[x].erase(q[x].begin() + i);
            break;
        }
    }
    for (int i = 0; i < q[y].size(); i++) {
        if (q[y][i] == x) {
            q[y].erase(q[y].begin() + i);
            break;
        }
    }
}

void add(int x, int y) {
    q[x].push_back(y);
    swap(q[x].front(), q[x].back());
    q[y].push_back(x);
    swap(q[y].front(), q[y].back());
}

void bfs2(int v) {
    queue <int> t;
    t.push(v);
    used2[v][v] = true;
    while (!t.empty()) {
        int z = t.front();
        t.pop();
        for (auto i : q[z]) {
            if (used2[v][i])
                continue;
            used2[v][i] = true;
            d2[v][i] = d2[v][z] + 1;
            t.push(i);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for (int i = 1; i <= n; i++) {
        make_set(i);
    }
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin>>x>>y;
        ed[i] = {x, y};
        if (find_set(x) == find_set(y)) {
            X = x, Y = y;
            continue;
        }
        q[x].pb(y);
        q[y].pb(x);
        union_set(x, y);
    }
    for (int i = 1; i <= n; i++) {
        make_set(i);
    }
    for (int i = n; i >= 1; i--) {
        int x = ed[i].fi, y = ed[i].se;
        if (find_set(x) == find_set(y)) {
            X2 = x, Y2 = y;
            continue;
        }
        union_set(x, y);
    }
    add(X, Y);
    for (int i = 1; i <= n; i++) {
        bfs(i);
    }
    del(X2, Y2);
    for (int i = 1; i <= n; i++) {
        bfs1(i);
    }
    add(X2, Y2);
    del(X, Y);
    for (int i = 1; i <= n; i++) {
        bfs2(i);
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            res = max(res, d[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (d[i][j] == res) {
                ans++;
                if (c[i][j] && d[i][j] == d2[i][j] && d[i][j] == d1[i][j]) {
                    ans++;
                }
            }
        }
    }
    cout<<ans;
}

Compilation message

shymbulak.cpp: In function 'void del(long long int, long long int)':
shymbulak.cpp:80:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q[x].size(); i++) {
                     ~~^~~~~~~~~~~~~
shymbulak.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q[y].size(); i++) {
                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 33656 KB Output is correct
2 Correct 61 ms 40932 KB Output is correct
3 Incorrect 106 ms 55800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 36 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -