oj.uz

답안 #781242

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
781242 2023-07-13T00:32:24 Z Programmer123 Islands (IOI08_islands) C++17
0 / 100
 80 ms 91160 KB 
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

#define int long long int
signed dest[1000000];
signed length[1000000];
std::vector<signed> backEdges[1000000];
std::bitset<1000000> seen;
int bestPath[1000000];
#ifdef LOCAL
#define debug std::cout
#else
#define debug std::stringstream()
#endif

void findComponent(signed node, std::vector<signed> &data) {
    if (seen[node]) return;
    data.push_back(node);
    seen[node] = true;
    findComponent(dest[node], data);
    for (auto x: backEdges[node]) {
        findComponent(x, data);
    }
}

int treeSum(int node) {
    int sum = 0;
    for (auto x: backEdges[node]) {
        if (!seen[x]) {
            sum += length[x] + treeSum(x);
        }
    }
    return sum;
}

int bestSingle(int node) {
    if (bestPath[node] != 0) {
        return bestPath[node];
    }
    int best = 0;
    for (auto x: backEdges[node]) {
        if (!seen[x]) {
            best = std::max(best, length[x] + bestSingle(x));
        }
    }
    return bestPath[node] = best;
}

int bestDouble(int node) {
    int best = 0;
    int secondBest = 0;
    std::vector<int> back;
    for (auto x: backEdges[node]) {
        if (!seen[x]) {
            int score = length[x] + bestSingle(x);
            if (score > best) {
                secondBest = best;
                best = score;
            } else if (score > secondBest) {
                secondBest = score;
            }
        }
    }
    return best + secondBest;
}
//Best score, assuming doesn't pass through edge between start and end of cycle.
int bestA(std::vector<signed> &cycle) {
    int best = 0;
    int current = 0;
    int bestBehind = 0;
    for (int i = 0; i < cycle.size(); ++i) {
        best = std::max(best, bestSingle(cycle[i]) + current + bestBehind);
        bestBehind = std::max(bestBehind, bestSingle(cycle[i]) - current);
        current += length[cycle[i]];
    }
    return best;
}

//Best score, assuming passes through edge between start and end of cycle
int bestB(std::vector<signed> &cycle) {
    int current = 0;
//    std::vector<int> lengthForward;
//    for (int i = 0; i < cycle.size() - 1; ++i) {
//        lengthForward.push_back(current);
//        current += length[cycle[i]];
//    }
    current = 0;
    std::vector<int> lengthBackward;
    for (int i = 0; i < cycle.size() - 1; ++i) {
        lengthBackward.push_back(current);
        current += length[cycle[cycle.size() - 2 - i]];
    }
    for (int i = 0; i < cycle.size() - 1; ++i) {
        //lengthForward[i] += bestSingle(cycle[i]);
        lengthBackward[i] += bestSingle(cycle[cycle.size() - 1 - i]);
    }
    for (int i = 1; i < cycle.size() - 1; ++i) {
        //lengthForward[i] = std::max(lengthForward[i], lengthForward[i - 1]);
        lengthBackward[i] = std::max(lengthBackward[i], lengthBackward[i - 1]);
    }
    int best = 0;
    int lengthForward = length[cycle[cycle.size() - 1]];
    int bestForward = lengthForward + bestSingle(cycle[0]);
    for (int i = 0; i < cycle.size() - 1; ++i) {
        best = std::max(best, bestForward + lengthBackward[cycle.size() - 2 - i]);
        lengthForward += length[cycle[i]];
        bestForward = std::max(bestForward, lengthForward + bestSingle(cycle[i + 1]));
    }
    return best;
}

int componentSum(const std::vector<signed> &component) {
    for (auto x: component) {
        seen[x] = false;
    }
    int root = component[0];
    while (!seen[root]) {
        seen[root] = true;
        root = dest[root];
    }
    for (auto x: component) {
        seen[x] = false;
    }
    std::vector<signed> cycle;
    cycle.push_back(root);
    seen[root] = true;
    for (int x = dest[root]; x != root; x = dest[x]) {
        cycle.push_back(x);
        seen[x] = true;
    }
    int best = 0;
    for (auto x: component) {
        best = std::max({best, bestDouble(x), bestSingle(x)});
    }
    best = std::max(best, bestA(cycle));
    best = std::max(best, bestB(cycle));
    for (auto x: component) {
        seen[x] = true;
    }
    return best;
}

signed main() {
#ifdef LOCAL
    freopen("INPUT", "r", stdin);
#else
    freopen("isl.in", "r", stdin);
    freopen("isl.out", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    //seen = new bool[N];
    for (signed i = 0; i < N; ++i) {
        seen[i] = false;
        signed x, l;
        std::cin >> x >> l;
        x--;
        dest[i] = x;
        length[i] = l;
        backEdges[x].push_back(i);
    }
    int total = 0;
    for (int i = 0; i < N; ++i) {
        if (!seen[i]) {
            std::vector<signed> component;
            findComponent(i, component);
            total += componentSum(component);
        }
    }
    std::cout << total << std::endl;
}

Compilation message

islands.cpp: In function 'long long int bestA(std::vector<int>&)':
islands.cpp:72:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < cycle.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
islands.cpp: In function 'long long int bestB(std::vector<int>&)':
islands.cpp:90:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int i = 0; i < cycle.size() - 1; ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~
islands.cpp:94:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < cycle.size() - 1; ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~
islands.cpp:98:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i = 1; i < cycle.size() - 1; ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~
islands.cpp:105:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i = 0; i < cycle.size() - 1; ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:148:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |     freopen("isl.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
islands.cpp:149:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |     freopen("isl.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 69 ms 91084 KB Execution killed with signal 6
2 Runtime error 69 ms 91104 KB Execution killed with signal 6
3 Runtime error 68 ms 91044 KB Execution killed with signal 6
4 Runtime error 68 ms 91140 KB Execution killed with signal 6
5 Runtime error 77 ms 91068 KB Execution killed with signal 6
6 Runtime error 70 ms 91072 KB Execution killed with signal 6
7 Runtime error 80 ms 91024 KB Execution killed with signal 6
8 Runtime error 71 ms 91020 KB Execution killed with signal 6
9 Runtime error 69 ms 91056 KB Execution killed with signal 6
10 Runtime error 70 ms 91056 KB Execution killed with signal 6
11 Runtime error 69 ms 91160 KB Execution killed with signal 6

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 78 ms 91104 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 79 ms 91056 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 71 ms 91028 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 76 ms 91024 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 69 ms 91084 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 69 ms 91136 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 69 ms 91084 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 73 ms 91140 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -