oj.uz

Submission #232727

# Submission time Handle Problem Language Result Execution time Memory
232727 2020-05-18T00:56:32 Z FieryPhoenix Islands (IOI08_islands) C++11
12 / 100
 917 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int N;
int L[1000001];
vector<pair<int,int>>adj[1000001];
bool vis[1000001];
ll ans,mx,mx2;
ll dis[1000001];
int prop,parStore;
pair<int,int>back; ll backCost;
int bad;

void dfs(int node, int par){
  //cout<<"dfs: "<<node<<' '<<par<<endl;
  vis[node]=true;
  vector<ll>v;
  for (auto p:adj[node]){
    if (vis[p.first]){
      if (p.first!=par && backCost==-1){
	back={p.first,node};
	prop=node;
	parStore=par;
	backCost=p.second;
      }
    }
    else{
      dfs(p.first,node);
      v.push_back(dis[p.first]+p.second);
    }
  }
  if (node==prop && par!=back.first)
    prop=par;
  if ((int)v.size()==0) return;
  sort(v.begin(),v.end());
  dis[node]=v.back();
  if (v.size()==1)
    mx=max(mx,v[0]);
  else
    mx=max(mx,v.back()+v[(int)v.size()-2]);
}

void dfs2(int node, int par, ll depth){
  mx2=max(mx2,depth);
  for (auto p:adj[node]){
    if (p.first==par || p.first==bad)
      continue;
    dfs2(p.first,node,depth+p.second);
  }
}

map<pair<int,int>,int>mp;

int main()
{
  //ios_base::sync_with_stdio(0);cin.tie(0);
  //freopen (".in","r",stdin);
  //freopen (".out","w",stdout);
  scanf("%d",&N);
  for (int i=1;i<=N;i++){
    int Y;
    scanf("%d%d",&Y,&L[i]);
    int x=i,y=Y;
    if (x>y) swap(x,y);
    mp[{x,y}]=max(mp[{x,y}],L[i]);
  }
  for (auto it:mp){
    adj[it.first.first].push_back({it.first.second,it.second});
    adj[it.first.second].push_back({it.first.first,it.second});
  }
  for (int i=1;i<=N;i++)
    if (!vis[i]){
      //cout<<"COMPONENT: "<<i<<endl;
      mx=0;
      backCost=-1;
      dfs(i,i);
      if (backCost==-1){
	ans+=mx;
	continue;
      }
      //cout<<"MX: "<<mx<<endl;
      mx2=0; bad=back.second;
      //cout<<"dfs2: "<<back.first<<' '<<prop<<endl;
      dfs2(back.first,prop,0);
      ll temp=mx2;
      mx2=0; bad=back.first;
      //cout<<"dfs2: "<<back.second<<' '<<parStore<<endl;
      dfs2(back.second,parStore,0);
      //cout<<"MX2: "<<temp<<' '<<mx2<<endl;
      mx=max(mx,mx2+temp+backCost);
      ans+=mx;
    }
  cout<<ans<<endl;
  return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&N);
   ~~~~~^~~~~~~~~
islands.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&Y,&L[i]);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 23808 KB Output isn't correct
2 Incorrect 18 ms 23936 KB Output isn't correct
3 Incorrect 19 ms 23936 KB Output isn't correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Incorrect 18 ms 23856 KB Output isn't correct
7 Incorrect 18 ms 23808 KB Output isn't correct
8 Incorrect 18 ms 23936 KB Output isn't correct
9 Incorrect 18 ms 23808 KB Output isn't correct
10 Correct 20 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 24064 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 25976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 32800 KB Output is correct
2 Incorrect 102 ms 38720 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 51972 KB Output is correct
2 Correct 210 ms 60224 KB Output is correct
3 Incorrect 265 ms 74744 KB Output isn't correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 877 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 917 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -