Submission #121445

#	Time	Username	Problem	Language	Result	Execution time	Memory
121445		TadijaSebez	Islands (IOI08_islands)	C++11	100 / 100	1048 ms	131072 KiB

islands

#include <stdio.h>
#include <vector>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
const int N=1000050;
const int M=2*N;
//vector<pair<int,int> > E[N];
int fir[N],go[M],tsz,l[M],g[M];
void Add(int u, int v, int w)
{
	tsz++;
	go[tsz]=fir[u];
	fir[u]=tsz;
	l[tsz]=w;
	g[tsz]=v;
}
void AddEdge(int u, int v, int w){ Add(u,v,w);Add(v,u,w);}
//vector<int> Cycle,len;
int Cycle[N],len[N],cnt;
bool on[N];
int disc[N],tid,par[N],add[N];
void FindCycle(int u)
{
	disc[u]=++tid;
	//par[u]=p;
	//add[u]=c;
	for(int i=fir[u];i;i=go[i])
	{
#define v g[i]
#define w l[i];
		//int v=E[u][i].first;
		//int w=E[u][i].second;
		if(!disc[v])
		{
			par[v]=u;
			add[v]=w;
			FindCycle(v);
		}
		else if(disc[v]>disc[u])
		{
			int x=v;
			cnt++;
			Cycle[cnt]=v;
			len[cnt]=add[v];
			on[v]=1;
			do
			{
				cnt++;
				x=par[x];
				Cycle[cnt]=x;
				if(x!=u) len[cnt]=add[x];
				else len[cnt]=w;
				on[x]=1;
			}while(x!=u);
		}
#undef v
#undef w
	}
}
ll diam;
ll max(ll a, ll b){ return a>b?a:b;}
bool done[N];
ll DFS(int u, int p)
{
	ll best=0;
	done[u]=1;
	for(int i=fir[u];i;i=go[i])
	{
#define v g[i]
#define w l[i]
		//int v=E[u][i].first;
		//int w=E[u][i].second;
		if(!on[v] && v!=p)
		{
			ll tmp=DFS(v,u);
			tmp+=w;
			diam=max(diam,tmp+best);
			best=max(best,tmp);
		}
#undef v
#undef w
	}
	return best;
}
ll sol,sz[N],u1[N],u2[N],v1[N],v2[N];
void Solve(int u)
{
	//Cycle.clear();len.clear();
	//Cycle.pb(0);len.pb(0);
	cnt=0;
	tid=0;
	FindCycle(u);
	diam=0;
	int n=cnt,i;
	for(i=1;i<=n;i++) sz[i]=DFS(Cycle[i],0);
	//printf("diam:%lld\n",diam);
	//for(i=1;i<=n;i++) printf("%i -> %i: %lld\n",Cycle[i],len[i],sz[i]);
	int bridge=len[n];
	ll best=0;
	ll sum=0;u1[0]=0;v1[0]=0;
	for(i=1;i<=n;i++)
	{
		u1[i]=max(u1[i-1],sz[i]+sum);
		v1[i]=max(v1[i-1],sz[i]+sum+best);
		best=max(best,sz[i]-sum);
		sum+=len[i];
	}
	best=sum=0;u2[n+1]=0;v2[n+1]=0;
	for(i=n;i>=1;i--)
	{
		u2[i]=max(u2[i+1],sz[i]+sum);
		v2[i]=max(v2[i+1],sz[i]+sum+best);
		best=max(best,sz[i]-sum);
		sum+=len[i-1];
	}
	diam=max(diam,v1[n]);
	for(i=1;i<n;i++) diam=max(diam,max(v1[i],max(v2[i+1],u1[i]+u2[i+1]+bridge)));
	sol+=diam;
	//printf("%i %lld\n",u,diam);
}
int main()
{
	int n,i,u,v,w;
	scanf("%i",&n);
	for(u=1;u<=n;u++) scanf("%i %i",&v,&w),AddEdge(u,v,w);//,E[u].pb(mp(v,w)),E[v].pb(mp(u,w));
	for(i=1;i<=n;i++) if(!done[i]) Solve(i);
	printf("%lld\n",sol);
	return 0;
}

Compilation message (stderr)

islands.cpp: In function 'int main()':
islands.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
islands.cpp:127:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(u=1;u<=n;u++) scanf("%i %i",&v,&w),AddEdge(u,v,w);//,E[u].pb(mp(v,w)),E[v].pb(mp(u,w));
                    ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10