Submission #197463

#	Time	Username	Problem	Language	Result	Execution time	Memory
197463		SamAnd	Islands (IOI08_islands)	C++17	0 / 100	28 ms	27772 KiB

islands

#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(const vector<int>& v)
{
    if (v.size() <= 1)
        return;
    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()
{
    freopen("input.txt", "r", stdin);
    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 (stderr)

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(const std::vector<int>&)':
islands.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < v.size(); ++i)
                     ~~^~~~~~~~~~
islands.cpp:92:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < v.size(); ++i)
                     ~~^~~~~~~~~~
islands.cpp:106: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:148:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vv.size(); ++i)
                     ~~^~~~~~~~~~~
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:153:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vv[i].size(); ++j)
                         ~~^~~~~~~~~~~~~~
islands.cpp:114:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
islands.cpp:119: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: 0 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10