oj.uz

답안 #232734

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232734 2020-05-18T02:37:48 Z FieryPhoenix Islands (IOI08_islands) C++11
12 / 100
 928 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;
int from[1000001];
vector<int>cycle,adjDis,deepest;
int bad,bad2;
ll maxCur;

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

ll maxDis,maxNode;

void findFarthest(int node, int 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(int node){
  maxDis=-1; maxNode=-1;
  findFarthest(node,node,0);
  int newNode=maxNode;
  maxDis=-1; maxNode=-1;
  findFarthest(newNode,newNode,0);
  return maxDis;
}

ll getDeep(int node, int 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<int,int>,int>mp;
ll pref[1000001],suff[1000001],pref2[1000001];

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;
      cycle.clear();
      adjDis.clear();
      deepest.clear();
      findCycle(i,i);
      //cout<<"Cycle: ";
      //for (int x:cycle)
      //	cout<<x<<' ';
      //cout<<endl;
      if (cycle.size()==0){
	//cout<<"multiEdge: "<<findDiameter(i)<<endl;
	ans+=findDiameter(i);
	continue;
      }
      maxCur=0;
      int C=cycle.size();
      for (int i=0;i<C;i++){
	pref[i]=0;
	suff[i]=0;
	pref2[i]=0;
	int inFront=cycle[(i+1)%C];
	int 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 (int i=0;i<C;i++){
	pref[i]=deepest[i];
	pref2[i]=pref[i];
	if (i>0){
	  pref[i]=max(pref[i],pref[i-1]+adjDis[i]);
	  pref2[i]=max(pref2[i],pref[i-1]);
	}
      }
      for (int i=C-1;i>=0;i--){
	suff[i]=deepest[i];
	if (i+1<C){
	  suff[i]=max(suff[i],suff[i+1]+adjDis[i]);
	  maxCur=max(maxCur,adjDis.back()+pref2[i]+suff[i+1]);
	}
      }
      ll sweep=0;
      for (int 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:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&N);
   ~~~~~^~~~~~~~~
islands.cpp:84: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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 23808 KB Output isn't correct
2 Runtime error 191 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Incorrect 18 ms 23936 KB Output isn't correct
4 Correct 19 ms 23808 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Incorrect 18 ms 23936 KB Output isn't correct
7 Runtime error 194 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 186 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Incorrect 18 ms 23808 KB Output isn't correct
10 Correct 18 ms 23808 KB Output is correct
11 Correct 18 ms 23936 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 881 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

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