oj.uz

Submission #121445

# Submission time Handle Problem Language Result Execution time Memory
121445 2019-06-26T14:16:11 Z TadijaSebez Islands (IOI08_islands) C++11
100 / 100
 1048 ms 131072 KB 
#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

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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 4 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1408 KB Output is correct
2 Correct 16 ms 3456 KB Output is correct
3 Correct 11 ms 1664 KB Output is correct
4 Correct 6 ms 1024 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4600 KB Output is correct
2 Correct 27 ms 7160 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 12712 KB Output is correct
2 Correct 62 ms 17804 KB Output is correct
3 Correct 80 ms 26104 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 23308 KB Output is correct
2 Correct 141 ms 42236 KB Output is correct
3 Correct 184 ms 50816 KB Output is correct
4 Correct 207 ms 66520 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 56084 KB Output is correct
2 Correct 744 ms 95480 KB Output is correct
3 Correct 243 ms 45176 KB Output is correct
4 Correct 460 ms 77592 KB Output is correct
5 Correct 295 ms 77188 KB Output is correct
6 Correct 1048 ms 54952 KB Output is correct
7 Correct 313 ms 102648 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 102904 KB Output is correct
2 Correct 310 ms 79468 KB Output is correct
3 Correct 394 ms 131072 KB Output is correct
4 Correct 282 ms 52472 KB Output is correct
5 Correct 292 ms 78576 KB Output is correct
6 Correct 267 ms 61700 KB Output is correct
7 Correct 1036 ms 55796 KB Output is correct