oj.uz

답안 #232742

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232742 2020-05-18T03:27:15 Z FieryPhoenix Islands (IOI08_islands) C++11
0 / 100
 854 ms 131072 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

ll N;
ll L[1000001];
vector<pair<ll,ll>>adj[1000001];
bool vis[1000001];
ll ans;
ll from[1000001];
vector<ll>cycle,adjDis,deepest;
ll bad,bad2;
ll maxCur;

void findCycle(ll node, ll par){
  //cout<<"findCycle: "<<node<<endl;
  vis[node]=true;
  for (auto p:adj[node]){
    if (cycle.size()==0 && vis[p.first] && p.first!=par){ //found cycle
      //cout<<"found cycle"<<endl;
      ll cur=node;
      while (cur!=p.first){
	cycle.push_back(cur);
	cur=from[cur];
      }
      cycle.push_back(p.first);
    }
    else if (!vis[p.first]){
      from[p.first]=node;
      findCycle(p.first,node);
    }
  }
}

ll maxDis,maxNode;

void findFarthest(ll node, ll par, ll dis){
  if (dis>maxDis){
    maxDis=dis;
    maxNode=node;
  }
  for (auto p:adj[node]){
    if (p.first!=par && p.first!=bad && p.first!=bad2)
      findFarthest(p.first,node,dis+p.second);
  }
}
    

ll findDiameter(ll node){
  maxDis=-1; maxNode=-1;
  findFarthest(node,node,0);
  ll newNode=maxNode;
  maxDis=-1; maxNode=-1;
  findFarthest(newNode,newNode,0);
  return maxDis;
}

ll getDeep(ll node, ll par, ll dis){
  ll mx=dis;
  for (auto p:adj[node]){
    if (p.first!=par && p.first!=bad && p.first!=bad2)
      mx=max(mx,getDeep(p.first,node,dis+p.second));
  }
  return mx;
}

map<pair<ll,ll>,ll>mp;
ll pref[1000001],suff[1000001],pref2[1000001],suff2[1000001];

int main()
{
  //ios_base::sync_with_stdio(0);cin.tie(0);
  //freopen (".in","r",stdin);
  //freopen (".out","w",stdout);
  scanf("%d",&N);
  for (ll i=1;i<=N;i++){
    ll Y;
    scanf("%d%d",&Y,&L[i]);
    ll x=i,y=Y;
    if (x>y) swap(x,y);
    mp[{x,y}]=max(mp[{x,y}],L[i]);
  }
  for (auto it:mp){
    //cout<<"edge: "<<it.first.first<<' '<<it.first.second<<endl;
    adj[it.first.first].push_back({it.first.second,it.second});
    adj[it.first.second].push_back({it.first.first,it.second});
  }
  for (ll i=1;i<=N;i++)
    if (!vis[i]){
      //cout<<"Component: "<<i<<endl;
      cycle.clear();
      adjDis.clear();
      deepest.clear();
      findCycle(i,i);
      /*
      cout<<"Cycle: ";
      for (ll x:cycle)
      	cout<<x<<' ';
      cout<<endl;
      */
      if (cycle.size()==0){
	//cout<<"multiEdge: "<<findDiameter(i)<<endl;
	ans+=findDiameter(i);
	continue;
      }
      maxCur=0;
      ll C=cycle.size();
      for (ll i=0;i<C;i++){
	pref[i]=0;
	suff[i]=0;
	pref2[i]=0;
	suff2[i]=0;
	ll inFront=cycle[(i+1)%C];
	ll inBack=cycle[(i-1+C)%C];
	adjDis.push_back(mp[{min(cycle[i],inFront),max(cycle[i],inFront)}]);
	bad=inFront;
	bad2=inBack;
	maxCur=max(maxCur,findDiameter(cycle[i]));
	deepest.push_back(getDeep(cycle[i],cycle[i],0));
      }
      for (ll i=0;i<C;i++){
	if (i>0){
	  pref[i]=pref[i-1]+adjDis[i-1];
	  pref2[i]=max(pref2[i-1],pref[i]+deepest[i]);
	}
	else
	  pref2[i]=deepest[i];
      }
      /*
      cout<<"deepest: "<<' ';
      for (ll x:deepest)
	cout<<x<<' ';
      cout<<endl;
      cout<<"adjDis: "<<' ';
      for (ll x:adjDis)
	cout<<x<<' ';
      cout<<endl;
      cout<<"pref: ";
      for (ll i=0;i<C;i++)
	cout<<pref[i]<<' ';
      cout<<endl;
      */
      for (ll i=C-1;i>=0;i--){
	if (i+1<C){
	  suff[i]=suff[i+1]+adjDis[i];
	  suff2[i]=max(suff2[i+1],suff[i]+deepest[i]);
	}
	else
	  suff2[i]=deepest[i];
      }
      for (ll i=0;i+1<C;i++){
	//cout<<i<<": "<<adjDis.back()<<' '<<pref2[i]<<' '<<suff2[i+1]<<endl;
	maxCur=max(maxCur,adjDis.back()+pref2[i]+suff2[i+1]);
      }
      ll sweep=0;
      for (ll i=0;i<C;i++){
	maxCur=max(maxCur,sweep+deepest[i]);
	sweep=max(sweep,(ll)deepest[i]);
	sweep+=adjDis[i];
      }
      ans+=maxCur;
      //cout<<"maxCur: "<<maxCur<<endl;
    }
  cout<<ans<<endl;
  return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:80:16: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
   scanf("%d",&N);
              ~~^
islands.cpp:83:26: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
     scanf("%d%d",&Y,&L[i]);
                  ~~      ^
islands.cpp:83:26: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
islands.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&N);
   ~~~~~^~~~~~~~~
islands.cpp:83: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
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 45 ms 48124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 45 ms 48072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 45 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 45 ms 48128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 46 ms 47992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 45 ms 47992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 46 ms 48000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 47 ms 47992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 45 ms 47992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 45 ms 48000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 45 ms 47996 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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