| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1037573 |
2024-07-29T04:53:30 Z |
8pete8 |
Islands (IOI08_islands) |
C++17 |
|
474 ms |
131072 KB |
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e6+5,inf=1e9,minf=-1e9,lg=25;
int n,m,k,x,y,q,z=0;
vector<pii>adj[mxn+10];
int dp[mxn+10][2][2],on[mxn+10],vis[mxn+10],have=0,up[mxn+10];
void dfs(int cur,int p){
vis[cur]=on[cur]=1;
for(auto i:adj[cur]){
if(i.f==p)continue;
if(vis[i.f]&&on[i.f]){
x=cur,y=i.f,z=i.s;
have++;
}
if(!vis[i.f])dfs(i.f,cur);
}
on[cur]=0;
}
void solve(int cur,int p){
int sum[2]={0,0};
vector<int>change[2];
for(auto i:adj[cur]){
if(i.f==p)continue;
if(have&(cur==x||i.f==y))continue;//delete the edge
up[i.f]=i.s;
solve(i.f,cur);
for(int j=0;j<2;j++){
sum[j]+=dp[i.f][0][j];
change[j].pb((dp[i.f][1][j])-dp[i.f][0][j]);
}
}
for(int j=0;j<2;j++)sort(all(change[j]));
//case where theres no extra edge
if(!change[0].empty())sum[0]+=change[0].back(),change[0].pop_back();
dp[cur][1][0]=sum[0]+up[cur];
if(!change[0].empty())sum[0]+=change[0].back(),change[0].pop_back();
dp[cur][0][0]=sum[0];
//have extra edge
if(!have)return;
if(cur==y||cur==x){
dp[cur][1][1]=sum[1]+up[cur];
if(!change[1].empty())sum[1]+=change[1].back(),change[1].pop_back();
dp[cur][0][1]=sum[1];
}
else{
if(!change[1].empty())sum[1]+=change[1].back(),change[1].pop_back();
dp[cur][1][1]=sum[1]+up[cur];
if(!change[1].empty())sum[1]+=change[1].back(),change[1].pop_back();
dp[cur][0][1]=sum[1];
}
}
map<pii,int>mp;
int32_t main(){
fastio
cin>>n;
for(int i=1;i<=n;i++){
int a,b;cin>>a>>b;
pii x={min(a,i),max(a,i)};
if(mp.find(x)==mp.end())mp[x]=b;
else mp[x]=max(mp[x],b);
}
for(auto i:mp){
adj[i.f.f].pb({i.f.s,i.s});
adj[i.f.s].pb({i.f.f,i.s});
}
int ans=0;
for(int i=1;i<=n;i++){
if(vis[i])continue;
have=0,z=0;
dfs(i,-1);
if(have>1)assert(0);//we should only have atmost 1 cycle?
solve(i,-1);
int mx=0;
for(int j=0;j<2;j++)for(int k=0;k<2;k++)mx=max(mx,dp[i][j][k]+(k*z));
ans+=mx;
}
cout<<ans<<'\n';
}
/*
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
a node cant be in multiple cycle
** there can be atmost 1 cycle for each comp
compute each comp independtly
how to solve a tree?
we can choose atmost 2 edge for each node
because each node can only be passed once
so dp[x][2]->take the parent edge or not
if y-> child of x
dp[x][0]=get 2 max(dp[y][1]) + other dp[y][0]
dp[x][1]=get 1 max(dp[y][1])+ other dp[y][0]
how to solve with 1 cycle?
we can try deleting 1 edge from the cycle to make a tree
so there are 2 cases delete or not delete if delete then do the dp on tree as usual just dont use that edge
if dont delete then we fix that edge so node a-b connected by that edge will only have get to choose 1 extra edge
*/
Compilation message
islands.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize ("03,unroll-lopps")
| ^
islands.cpp:39:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
39 | void dfs(int cur,int p){
| ^
islands.cpp:51:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
51 | void solve(int cur,int p){
| ^
islands.cpp:85:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
85 | int32_t main(){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
29272 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
29272 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
29276 KB |
Output isn't correct |
| 4 |
Correct |
4 ms |
29276 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
29272 KB |
Output isn't correct |
| 6 |
Incorrect |
4 ms |
29136 KB |
Output isn't correct |
| 7 |
Incorrect |
4 ms |
29276 KB |
Output isn't correct |
| 8 |
Incorrect |
5 ms |
29276 KB |
Output isn't correct |
| 9 |
Incorrect |
4 ms |
29276 KB |
Output isn't correct |
| 10 |
Incorrect |
4 ms |
29316 KB |
Output isn't correct |
| 11 |
Correct |
4 ms |
29276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
29276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
29528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
31648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
37208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
59196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
198 ms |
107084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
474 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
448 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
