oj.uz

답안 #197459

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197459 2020-01-21T11:34:56 Z SamAnd Islands (IOI08_islands) C++17
90 / 100
 1199 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 1000006;
const long long INF = 1000000009000000009;
struct ban
{
    int x;
    long long d;
    ban(){}
    ban(int x, long long d)
    {
        this->x = x;
        this->d = d;
    }
};

int n;
int uu[N], dd[N];
vector<ban> a[N];

vector<vector<int> > vv;

int c[N];

int p[N];
int s, f;
bool dfs(int x)
{
    c[x] = 1;
    int h = uu[x];
    if (c[h] == 1)
    {
        s = h;
        f = x;
        c[x] = 2;
        return true;
    }
    if (c[h] == 0)
    {
        p[h] = x;
        if (dfs(h))
        {
            c[x] = 2;
            return true;
        }
    }
    c[x] = 2;
    return false;
}

long long yans;

long long dp[N];
void dfs1(int x, int p)
{
    long long max1 = 0, max2 = 0;
    for (int i = 0; i < a[x].size(); ++i)
    {
        ban h = a[x][i];
        if (h.x == p || c[h.x])
            continue;
        dfs1(h.x, x);
        dp[x] = max(dp[x], h.d + dp[h.x]);
        if (h.d + dp[h.x] >= max1)
        {
            max2 = max1;
            max1 = h.d + dp[h.x];
        }
        else if (h.d + dp[h.x] >= max2)
            max2 = h.d + dp[h.x];
    }
    yans = max(yans, max1 + max2);
    yans = max(yans, dp[x]);
}

long long pp[N], ss[N];
void solvv(vector<int> v)
{
    vector<int> vv;
    long long maxu = dp[v[0]];
    for (int i = 1; i < v.size(); ++i)
    {
        int d = dd[v[i - 1]];
        maxu += d;
        yans = max(yans, maxu + dp[v[i]]);
        maxu = max(maxu, dp[v[i]]);
    }
    long long u = 0;
    pp[0] = dp[v[0]];
    for (int i = 1; i < v.size(); ++i)
    {
        int d = dd[v[i - 1]];
        u += d;
        pp[i] = max(pp[i - 1], u + dp[v[i]]);
    }
    u = 0;
    ss[v.size() - 1] = dp[v.back()];
    for (int i = v.size() - 2; i >= 0; --i)
    {
        int d = dd[v[i]];
        u += d;
        ss[i] = max(ss[i + 1], u + dp[v[i]]);
    }
    for (int i = 0; i < v.size() - 1; ++i)
    {
        yans = max(yans, pp[i] + ss[i + 1] + dd[v.back()]);
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        int x, d;
        scanf("%d%d", &x, &d);
        uu[i] = x;
        dd[i] = d;
        a[i].push_back(ban(x, d));
        a[x].push_back(ban(i, d));
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!c[i])
        {
            if (dfs(i))
            {
                vector<int> v;
                for (int x = f; x != s; x = p[x])
                    v.push_back(x);
                v.push_back(s);
                reverse(v.begin(), v.end());
                vv.push_back(v);
            }
        }
    }
    /*for (int i = 0; i < vv.size(); ++i)
    {
        for (int j = 0; j < vv[i].size(); ++j)
            printf("%d ", vv[i][j]);
        printf("\n");
    }*/
    long long ans = 0;
    memset(c, 0, sizeof c);
    for (int i = 0; i < vv.size(); ++i)
    {
        yans = 0;
        for (int j = 0; j < vv[i].size(); ++j)
            c[vv[i][j]] = 1;
        for (int j = 0; j < vv[i].size(); ++j)
            dfs1(vv[i][j], vv[i][j]);
        solvv(vv[i]);
        ans += yans;
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message

islands.cpp: In function 'void dfs1(int, int)':
islands.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
islands.cpp: In function 'void solvv(std::vector<int>)':
islands.cpp:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < v.size(); ++i)
                     ~~^~~~~~~~~~
islands.cpp:91:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < v.size(); ++i)
                     ~~^~~~~~~~~~
islands.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size() - 1; ++i)
                     ~~^~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:146:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vv.size(); ++i)
                     ~~^~~~~~~~~~~
islands.cpp:149:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vv[i].size(); ++j)
                         ~~^~~~~~~~~~~~~~
islands.cpp:151:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vv[i].size(); ++j)
                         ~~^~~~~~~~~~~~~~
islands.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
islands.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &d);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 27768 KB Output is correct
2 Correct 33 ms 27768 KB Output is correct
3 Correct 27 ms 27768 KB Output is correct
4 Correct 28 ms 27828 KB Output is correct
5 Correct 27 ms 27772 KB Output is correct
6 Correct 27 ms 27768 KB Output is correct
7 Correct 28 ms 27768 KB Output is correct
8 Correct 27 ms 27700 KB Output is correct
9 Correct 27 ms 27768 KB Output is correct
10 Correct 27 ms 27768 KB Output is correct
11 Correct 28 ms 27868 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 27896 KB Output is correct
2 Correct 28 ms 27996 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 27996 KB Output is correct
2 Correct 34 ms 28152 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 29176 KB Output is correct
2 Correct 50 ms 31352 KB Output is correct
3 Correct 42 ms 29560 KB Output is correct
4 Correct 34 ms 28664 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 32884 KB Output is correct
2 Correct 75 ms 36756 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 45088 KB Output is correct
2 Correct 135 ms 47504 KB Output is correct
3 Correct 171 ms 55444 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 61816 KB Output is correct
2 Correct 275 ms 77152 KB Output is correct
3 Correct 295 ms 80276 KB Output is correct
4 Correct 375 ms 98624 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 439 ms 98220 KB Output is correct
2 Correct 919 ms 131072 KB Output is correct
3 Correct 422 ms 96760 KB Output is correct
4 Correct 548 ms 124232 KB Output is correct
5 Correct 523 ms 124256 KB Output is correct
6 Correct 1199 ms 112760 KB Output is correct
7 Correct 569 ms 131072 KB Output is correct

Subtask #9
0 / 10.0

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