답안 #201181

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
201181 2020-02-09T15:49:36 Z a_player Islands (IOI08_islands) C++14
0 / 100
2000 ms 23928 KB
#include <bits/stdc++.h>
#define f first
#define s second.first
#define tr second.second
#define mp make_pair

using namespace std;


ofstream out("output.txt");

const int MAXN =1e6+1;
typedef long long ll;

int read(){
    int r=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    r=ch-'0';
    ch=getchar();
    while(ch>='0'&&ch<='9'){
        r=r*10+ch-'0';
        ch=getchar();
    }
    return r;
}

vector<pair<int,pair<ll,int> > > grafo[MAXN];
ll m[MAXN][4];
deque<int> cyc;
ll succ[MAXN];
bitset<MAXN> v;
bitset<MAXN> k;
ll zipp[MAXN];
int pos[MAXN];
bool find_cyc(int n, int pa){
    v[n]=1;
    k[n]=1;
    cyc.push_back(n);
    for(auto x:grafo[n]){
        if(!v[x.f]){
        if(find_cyc(x.f,x.tr))return true;
        }
        else if(x.tr!=pa){
            cyc.push_back(x.f);
            return true;
        }
    }
    cyc.pop_back();
    return false;
}
ll zip(int n, int a, int b, int c){
    k[n]=1;
    ll mas=0;
    for(auto x:grafo[n]){
        if(x.f==a||x.f==b||x.f==c)continue;
        mas=max(mas,zip(x.f,n,b,c)+x.s);
    }
    return mas;
}
ll dfs(int n, int a){
    ll mas=0;
    pos[n]=-1;
    k[n]=1;
    for(auto x:grafo[n]){
        if(n==cyc.front()&&x.f==cyc.back())continue;
        if(x.f==cyc.front()&&n==cyc.back())continue;
        if(x.f==a)continue;
        ll p=dfs(x.f,n)+x.s;
        if(mas<p){
            mas=p;
            pos[n]=pos[x.f];
        }
    }
    if(pos[n]==-1)pos[n]=n;
    return mas;
}
ll dfs2(int n, int a, int w){
    ll mas=0;
    pos[n]=-1;
    k[n]=1;
    for(auto x:grafo[n]){
        if(n==cyc.front()&&x.f==cyc.back()&&x.s!=w)continue;
        if(x.f==cyc.front()&&n==cyc.back()&&x.s!=w)continue;
        if(x.f==a)continue;
        ll p=dfs2(x.f,n,w)+x.s;
        if(mas<p){
            mas=p;
            pos[n]=pos[x.f];
        }
    }
    if(pos[n]==-1)pos[n]=n;
    return mas;
}
int N;
ll process(int t){
    cyc.clear();
    find_cyc(t,-1);
    while(cyc.front()!=cyc.back())cyc.pop_front();
    cyc.pop_front();
    zipp[cyc[0]]=zip(cyc[0],-1,cyc[1],cyc.back());
    for(int i=1;i<cyc.size()-1;i++)zipp[cyc[i]]=zip(cyc[i],-1,cyc[i-1],cyc[i+1]);
    zipp[cyc.back()]=zip(cyc.back(),-1,cyc[cyc.size()-2],cyc.front());
    if(cyc.size()==2){
        ll mass=0;
    for(auto x:grafo[cyc[0]])
    if(x.f==cyc[1]){
        mass=max(mass,x.s);
    }
    dfs2(t,-1,mass);
    return dfs2(pos[t],-1,mass);
    }
    for(int i=1;i<cyc.size()-1;i++)
    for(auto x:grafo[cyc[i]])
    if(x.f==cyc[i+1]){
        succ[cyc[i]]=x.s;
        break;
    }
    ll speciale=0;
    for(auto x:grafo[cyc[0]]){
        if(x.f==cyc[1])succ[cyc[0]]=x.s;
        if(x.f==cyc.back())speciale=x.s;
    }
    int se=cyc.size();
    m[cyc[0]][0]=0;
    for(int i=1;i<se;i++)m[cyc[i]][0]=m[cyc[i-1]][0]+succ[cyc[i-1]];
    m[cyc[0]][1]=zipp[cyc[0]];
    for(int i=1;i<se;i++)m[cyc[i]][1]=max(m[cyc[i-1]][1],m[cyc[i]][0]+zipp[cyc[i]]);
    m[cyc.back()][2]=0;
    for(int i=se-2;i>=0;i--)m[cyc[i]][2]=m[cyc[i+1]][2]+succ[cyc[i]];
    m[cyc.back()][3]=zipp[cyc.back()];
    for(int i=se-2;i>=0;i--)m[cyc[i]][3]=max(m[cyc[i+1]][3],m[cyc[i]][2]+zipp[cyc[i]]);
    
    ll ans=0;
    for(int i=0;i<se-1;i++)ans=max(ans,m[cyc[i]][1]+m[cyc[i+1]][3]+speciale);
    dfs(t,-1);
    ans=max(ans,dfs(pos[t],-1));
    return ans;
}
int main(){
    freopen("input.txt","r",stdin);
    N=read();
    for(int i=0;i<N;i++){
        int a,c;
        a=read(),c=read();
        a--;
        grafo[a].push_back(mp(i,mp((ll)c,i)));
        grafo[i].push_back(mp(a,mp((ll)c,i)));
    }
    ll ans=0;
    for(int i=0;i<N;i++)
    if(!k[i])ans+=process(i);
    out<<ans;

}

Compilation message

islands.cpp: In function 'll process(int)':
islands.cpp:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<cyc.size()-1;i++)zipp[cyc[i]]=zip(cyc[i],-1,cyc[i-1],cyc[i+1]);
                 ~^~~~~~~~~~~~~
islands.cpp:113:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<cyc.size()-1;i++)
                 ~^~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:141:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2087 ms 23800 KB Time limit exceeded
2 Execution timed out 2088 ms 23800 KB Time limit exceeded
3 Execution timed out 2073 ms 23800 KB Time limit exceeded
4 Execution timed out 2086 ms 23928 KB Time limit exceeded
5 Execution timed out 2092 ms 23800 KB Time limit exceeded
6 Execution timed out 2079 ms 23800 KB Time limit exceeded
7 Execution timed out 2083 ms 23800 KB Time limit exceeded
8 Execution timed out 2086 ms 23800 KB Time limit exceeded
9 Execution timed out 2091 ms 23800 KB Time limit exceeded
10 Execution timed out 2096 ms 23800 KB Time limit exceeded
11 Execution timed out 2091 ms 23804 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2095 ms 23800 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2083 ms 23800 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2089 ms 23928 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2087 ms 23800 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2091 ms 23928 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2082 ms 23800 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2091 ms 23800 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2088 ms 23928 KB Time limit exceeded
2 Halted 0 ms 0 KB -