답안 #201185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
201185	2020-02-09T15:59:06 Z	a_player	Islands (IOI08_islands)	C++14	컴파일 오류	0 ms	0 KB

islands

#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];
map<int,ll> m[4];
deque<int> cyc;
map<int,ll> succ;
bitset<MAXN> v;
bitset<MAXN> k;
map<int,ll> zip;
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[0][cyc[0]]=0;
    for(int i=1;i<se;i++)m[0][cyc[i]]=m[0][cyc[i-1]]+succ[cyc[i-1]];
    m[1][cyc[0]]=zipp[cyc[0]];
    for(int i=1;i<se;i++)m[1][cyc[i]]=max(m[1][cyc[i-1]],m[0][cyc[i]]+zipp[cyc[i]]);
    m[2][cyc.back()]=0;
    for(int i=se-2;i>=0;i--)m[2][cyc[i]]=m[2][cyc[i+1]]+succ[cyc[i]];
    m[3][cyc.back()]=zipp[cyc.back()];
    for(int i=se-2;i>=0;i--)m[3][cyc[i]]=max(m[3][cyc[i+1]],m[2][cyc[i]]+zipp[cyc[i]]);
    
    ll ans=0;
    for(int i=0;i<se-1;i++)ans=max(ans,m[1][cyc[i]]+m[3][cyc[i+1]]+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);
    cout<<ans;

}

Compilation message

islands.cpp: In function 'll zip(int, int, int, int)':
islands.cpp:52:34: error: 'll zip(int, int, int, int)' redeclared as different kind of symbol
 ll zip(int n, int a, int b, int c){
                                  ^
islands.cpp:34:13: note: previous declaration 'std::map<int, long long int> zip'
 map<int,ll> zip;
             ^~~
islands.cpp:57:34: error: no match for call to '(std::map<int, long long int>) (int&, int&, int&, int&)'
         mas=max(mas,zip(x.f,n,b,c)+x.s);
                                  ^
islands.cpp: In function 'll process(int)':
islands.cpp:101:5: error: 'zipp' was not declared in this scope
     zipp[cyc[0]]=zip(cyc[0],-1,cyc[1],cyc.back());
     ^~~~
islands.cpp:101:5: note: suggested alternative: 'zip'
     zipp[cyc[0]]=zip(cyc[0],-1,cyc[1],cyc.back());
     ^~~~
     zip
islands.cpp:101:49: error: no match for call to '(std::map<int, long long int>) (__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&, int, __gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&, __gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&)'
     zipp[cyc[0]]=zip(cyc[0],-1,cyc[1],cyc.back());
                                                 ^
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:102:80: error: no match for call to '(std::map<int, long long int>) (__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&, int, __gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&, __gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&)'
     for(int i=1;i<cyc.size()-1;i++)zipp[cyc[i]]=zip(cyc[i],-1,cyc[i-1],cyc[i+1]);
                                                                                ^
islands.cpp:103:69: error: no match for call to '(std::map<int, long long int>) (__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&, int, __gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&, __gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&)'
     zipp[cyc.back()]=zip(cyc.back(),-1,cyc[cyc.size()-2],cyc.front());
                                                                     ^
islands.cpp:113:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<cyc.size()-1;i++)
                 ~^~~~~~~~~~~~~