oj.uz

Submission #74609

# Submission time Handle Problem Language Result Execution time Memory
74609 2018-09-05T07:42:20 Z wzy Islands (IOI08_islands) C++11
70 / 100
 420 ms 132096 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int,int>
int pai[1000005] , peso[1000005] , n;
vector<pii> adj[1000005];
vector<int> nodescomponente[1000005];
ll dg[1000005] , dp[1000005] , f[1000005];
bitset<1000005> foicmp , vis;
vector<int> cycleshift;
int poscycle[1000005];
int cntz = 0;
vector<ll> pfsx;
deque<ll> aux , aux2;

void refreshaux(){
	while(!aux.empty()) aux.pop_back();
}

void refreshaux2(){
	while(!aux2.empty()) aux2.pop_back();
}

ll auxquery(){
	return aux.front();
}

ll aux2query(){
	return aux2.front();
}

inline int read_int() {
   register char c=0;
   int a=0;
   while (c<33) c=getchar();
   while (c>33) {
       a=a*10+c-'0', c=getchar();
   }
   return a;
}

void auxinsert(ll x){
	while(aux.size() && x >= aux.back()) aux.pop_back();
	aux.push_back(x);
	return;
}
ll lst;

void aux2insert(ll x){
	while(aux2.size() && x >= aux2.back()) aux2.pop_back();
	aux2.push_back(x);
	return;
}


int sttx;
int fd(int x){
	return pai[x] == x ? x : pai[x] = fd(pai[x]);
}

void join(int x , int y){
	x = fd(x) , y = fd(y);
	if(peso[x] > peso[y]) swap(x,y);
	pai[x] = y, peso[y] += peso[x] + 1;
}

ll farnodedist = -1 , farnode = -1;

void dfs1(int x, int y , ll z){
	if(z >= farnodedist){
		farnode = x;
		farnodedist = z;
	}
	for(int j = 0 ; j < adj[x].size();j++){
		pii v = adj[x][j];
		if(poscycle[v.S] != -1 && v.S != sttx) continue;
		if(v.S == y) continue;
		dfs1(v.S,x, z + v.F);
	}
}

void dfs2(int x){
	cycleshift.pb(x);
	vis[x] = true;
	int anterior = 0;
	int candoit = false;
	poscycle[x] = ((int)cycleshift.size()) - 1;
	for(int j = 0 ; j < adj[x].size() ; j++){
		int v = adj[x][j].S;
		if(v == cycleshift.front()){
			anterior = 1;
		}
		if(!vis[v]){
			candoit = true;
			pfsx.pb(adj[x][j].F);
			dfs2(v);
			break;
		}
	}
	if(!candoit && anterior) lst = x;
}

long long solve(int cc){
	queue<int> q;
	for(int i = 0 ; i < nodescomponente[cc].size() ;i ++){
		int v = nodescomponente[cc][i];
		if(dg[v] == 1){
			q.push(v);
			dp[v] = 0;
		}
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(int j = 0 ; j < adj[u].size() ;j++){
			pii v = adj[u][j];
			if(vis[v.S]) continue;
			dg[v.S]--;
			dp[v.S] = max(dp[v.S] , dp[u] + v.F);
			if(dg[v.S] == 1) q.push(v.S);
		}
	}
	cntz = 0;
	pfsx.clear();
	cycleshift.clear();
	for(int i = 0 ; i <nodescomponente[cc].size();i++){
		if(!vis[nodescomponente[cc][i]]){
			dfs2(nodescomponente[cc][i]);
		}
	}
	for(int j = 0 ; j < adj[cycleshift.back()].size();j++){
		if(adj[cycleshift.back()][j].S == cycleshift.front()){
			lst = adj[cycleshift.back()][j].F;
		}
	}
	for(int j = 0 ; j < cycleshift.size() ; j++){
		f[cycleshift[j]] = 0;
	}
	for(int j = 0 ; j < pfsx.size() ; j++){
		if(j) pfsx[j] += pfsx[j-1];
	}
	refreshaux();
	refreshaux2();
	ll somaj = pfsx.back() + lst;
	for(int i = 0 ; i < cycleshift.size();i ++){
		if(i){
			ll t = auxquery();
			f[cycleshift[i]] = max(f[cycleshift[i]] , dp[cycleshift[i]] + pfsx[i-1] +t);
			t = aux2query();
			f[cycleshift[i]] = max(f[cycleshift[i]] , dp[cycleshift[i]] +t - pfsx[i-1]);
			aux2insert(-(-dp[cycleshift[i]] - somaj - pfsx[i-1]));
			auxinsert(-(-dp[cycleshift[i]] +pfsx[i-1]));
		}
		else auxinsert(-(-dp[cycleshift.front()] )) , aux2insert(-(-dp[cycleshift.front()] - somaj));
	}
	ll ansj = -1;
	for(vector<int>::iterator it = cycleshift.begin() ; it != cycleshift.end() ; it++){
		int v = *it;
		farnode = -1 , farnodedist = -1;
		 sttx = v;
		dfs1(v , v , 0);
		int tt = farnode;
		farnode = - 1 , farnodedist = -1;
		dfs1(tt,  tt , 0);
		ansj = max(ansj , farnodedist);
		ansj = max(ansj , f[v]);
	}
	return ansj;
}

int32_t main(){
	n = read_int();
	for(int i = 0 ; i <n;i++) pai[i] = i , peso[i] = 0, poscycle[i] = -1;
	for(int i = 1 ; i <=n;i++){
		int x , z;
		x = read_int();
		z = read_int();
		adj[x-1].pb(pii(z,i-1));
		adj[i-1].pb(pii(z,x-1));
		dg[i-1]++;
		dg[x-1]++;
		join(x-1 , i-1);
	}
	for(int i = 0 ; i < n;i++){
		nodescomponente[fd(i)].pb(i);
	}
	long long ans = 0;
	for(int i = 0 ;  i < n; i++){
		if(!foicmp[fd(i)]) ans += solve(fd(i)) , foicmp[fd(i)] = true;
	}
	printf("%lld\n" , ans);
}

Compilation message

islands.cpp: In function 'void dfs1(int, int, long long int)':
islands.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < adj[x].size();j++){
                  ~~^~~~~~~~~~~~~~~
islands.cpp: In function 'void dfs2(int)':
islands.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < adj[x].size() ; j++){
                  ~~^~~~~~~~~~~~~~~
islands.cpp: In function 'long long int solve(int)':
islands.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < nodescomponente[cc].size() ;i ++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:120:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < adj[u].size() ;j++){
                   ~~^~~~~~~~~~~~~~~
islands.cpp:131:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i <nodescomponente[cc].size();i++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:136:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < adj[cycleshift.back()].size();j++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:141:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < cycleshift.size() ; j++){
                  ~~^~~~~~~~~~~~~~~~~~~
islands.cpp:144:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < pfsx.size() ; j++){
                  ~~^~~~~~~~~~~~~
islands.cpp:150:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < cycleshift.size();i ++){
                  ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 43 ms 47392 KB Output is correct
4 Correct 45 ms 47400 KB Output is correct
5 Correct 44 ms 47456 KB Output is correct
6 Correct 45 ms 47564 KB Output is correct
7 Correct 43 ms 47564 KB Output is correct
8 Correct 43 ms 47748 KB Output is correct
9 Correct 43 ms 47748 KB Output is correct
10 Correct 43 ms 47748 KB Output is correct
11 Correct 48 ms 47748 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47816 KB Output is correct
2 Correct 44 ms 47816 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47912 KB Output is correct
2 Correct 47 ms 48264 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 49344 KB Output is correct
2 Correct 65 ms 52492 KB Output is correct
3 Correct 55 ms 52492 KB Output is correct
4 Correct 48 ms 52492 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 55148 KB Output is correct
2 Correct 84 ms 59704 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 70260 KB Output is correct
2 Correct 140 ms 76452 KB Output is correct
3 Correct 164 ms 91352 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 95312 KB Output is correct
2 Correct 252 ms 126164 KB Output is correct
3 Runtime error 271 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 395 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 420 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -