oj.uz

답안 #118092

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118092 2019-06-18T07:23:39 Z baluteshih Islands (IOI08_islands) C++14
12 / 100
 437 ms 131072 KB 
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct mode
{
	int F,S,num;
};

vector<mode> G[1000005];
vector<pll> cir;
vector<ll> len;
bitset<1000005> yc;
ll M,dft,dfn[1000005];
const ll INF=1e18;

bool dfs(int u,int f)
{
	int flag=0;
	dfn[u]=++dft;
	for(auto i:G[u])
		if(i.num!=f)
			if(!dfn[i.F])
				if(dfs(i.F,i.num))
					flag=1,len.pb(i.S);
				else;
			else if(dfn[i.F]<dfn[u])
				flag=1,yc[i.F]=1,cir.pb(MP(i.F,0)),len.pb(i.S);
	if(flag)
		if(yc[u]) flag=0;
		else cir.pb(MP(u,0)),yc[u]=1;
	return flag;
}

ll dfs2(int u)
{
	ll mx=0,sx=0;
	yc[u]=1;
	for(auto i:G[u])
		if(!yc[i.F])
		{
			ll d=dfs2(i.F)+i.S;
			if(d>mx) sx=mx,mx=d;
			else if(d>sx) sx=d;
		}
	M=max(M,sx+mx);
	return mx;
}

int main()
{jizz
	ll n,a,w,ans=0,sum;
	cin >> n;
	for(int i=1;i<=n;++i)
		cin >> a >> w,G[i].pb(mode{a,w,i}),G[a].pb(mode{i,w,i});
	for(int i=1;i<=n;++i)
		if(!dfn[i])
		{
			cir.clear(),len.clear(),M=0,dfs(i,i);
			for(int j=0;j<cir.size();++j)
				cir[j].S=dfs2(cir[j].F);
			int n=cir.size();
			deque<pll> dq;
			sum=0,dq.pb(MP(0,cir[0].S));
			for(int j=0;j<n;++j)	
				cir.pb(cir[j]),len.pb(len[j]);
			for(int j=1;j<cir.size();++j)
			{
				while(dq.size()&&j-dq[0].F>=n) dq.pop_front();
				sum+=len[j-1],M=max(M,sum+cir[j].S+dq[0].S);
				while(dq.size()&&cir[j].S-sum>=dq.back().S)
					dq.pop_back();
				dq.pb(MP(j,cir[j].S-sum));
			}
			ans+=M;
		}
	cout << ans << "\n";
}

Compilation message

islands.cpp: In function 'bool dfs(int, int)':
islands.cpp:33:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   if(i.num!=f)
     ^
islands.cpp:40:4: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  if(flag)
    ^
islands.cpp: In function 'int main()':
islands.cpp:66:35: warning: narrowing conversion of 'a' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
   cin >> a >> w,G[i].pb(mode{a,w,i}),G[a].pb(mode{i,w,i});
                                   ^
islands.cpp:66:35: warning: narrowing conversion of 'w' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
islands.cpp:66:56: warning: narrowing conversion of 'w' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
   cin >> a >> w,G[i].pb(mode{a,w,i}),G[a].pb(mode{i,w,i});
                                                        ^
islands.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<cir.size();++j)
                ~^~~~~~~~~~~
islands.cpp:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=1;j<cir.size();++j)
                ~^~~~~~~~~~~

Subtask #1
12.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Runtime error 49 ms 47608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 22 ms 24064 KB Output is correct
4 Runtime error 49 ms 47608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 22 ms 23808 KB Output is correct
6 Incorrect 22 ms 23808 KB Output isn't correct
7 Incorrect 22 ms 23780 KB Output isn't correct
8 Runtime error 48 ms 47608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 22 ms 23808 KB Output isn't correct
10 Runtime error 48 ms 47480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Correct 22 ms 23928 KB Output is correct

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 47 ms 47584 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 49 ms 47656 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 49016 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 68 ms 52588 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 115 ms 66600 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 Correct 177 ms 51196 KB Output is correct
2 Runtime error 224 ms 97488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 370 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 437 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -