oj.uz

Submission #1036154

# Submission time Handle Problem Language Result Execution time Memory
1036154 2024-07-27T04:20:40 Z 12345678 Islands (IOI08_islands) C++17
21 / 100
 2000 ms 131072 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;

#define ll long long

int vs[nx], n, x, cnt, rt;
ll w, mx[nx], pw[nx], ans;
vector<tuple<int, int, ll>> d[nx];
vector<pair<int, ll>> c;

bool dfs(int u, int pidx)
{
    vs[u]=1;
    for (auto [v, idx, w]:d[u])
    {
        if (idx==pidx) continue;
        if (!vs[v]) 
        {
            pw[v]=w;
            //cout<<"here "<<u<<' '<<v<<' '<<w<<'\n', 
            if (dfs(v, u)) vs[u]=2; 
        }
        else if (vs[v]==1) pw[v]=w, vs[u]=2, rt=v;
    }
    if (vs[u]==2) c.push_back({u, pw[u]});
    if (vs[u]==2&&u!=rt) return 1;
    return 0;
}

void dfs2(int u, int pidx)
{
    for (auto [v, idx, w]:d[u]) if (idx!=pidx&&vs[v]==1) dfs2(v, idx), mx[u]=max(mx[u], mx[v]+w);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>x>>w, d[i].push_back({x, i, w}), d[x].push_back({i, i, w});
    for (int i=1; i<=n; i++) 
    {
        if (!vs[i]) 
        {
            c.clear();
            dfs(i, -1);
            for (auto [u, p]:c) dfs2(u, -1);
            //for (auto x:c) cout<<"cy "<<x.first<<' '<<x.second<<'\n';
            reverse(c.begin(), c.end());
            for (int i=2; i<c.size(); i++) c[i].second+=c[i-1].second;
            ll sm=c[0].second+c[c.size()-1].second, tmp=0;
            c[0].second=0;
            //for (auto x:c) cout<<"cy "<<x.first<<' '<<x.second<<'\n';
            //cout<<"sm "<<sm<<'\n';
            for (int j=0; j<c.size(); j++)
            {
                for (int k=j+1; k<c.size(); k++)
                {
                    tmp=max(tmp, mx[c[j].first]+mx[c[k].first]+max(c[k].second-c[j].second, sm-(c[k].second-c[j].second)));
                }
            }
            //cout<<"debug "<<i<<' '<<tmp<<'\n';
            ans+=tmp;
        }
    }
    cout<<ans;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:52:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for (int i=2; i<c.size(); i++) c[i].second+=c[i-1].second;
      |                           ~^~~~~~~~~
islands.cpp:57:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for (int j=0; j<c.size(); j++)
      |                           ~^~~~~~~~~
islands.cpp:59:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                 for (int k=j+1; k<c.size(); k++)
      |                                 ~^~~~~~~~~

Subtask #1
21.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Incorrect 9 ms 23900 KB Output isn't correct
3 Correct 10 ms 23800 KB Output is correct
4 Incorrect 15 ms 23968 KB Output isn't correct
5 Correct 10 ms 23792 KB Output is correct
6 Correct 9 ms 23836 KB Output is correct
7 Correct 9 ms 23796 KB Output is correct
8 Incorrect 10 ms 23896 KB Output isn't correct
9 Correct 10 ms 23896 KB Output is correct
10 Incorrect 10 ms 23900 KB Output isn't correct
11 Correct 10 ms 23900 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 23896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 25436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 867 ms 30680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2050 ms 43200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1579 ms 56276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 91308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 236 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -