oj.uz

답안 #715314

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715314 2023-03-26T12:07:11 Z Ahmed57 Islands (IOI08_islands) C++17
70 / 100
 765 ms 131072 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

using namespace std;
stack<int> st;
vector<vector<int>> all;
vector<pair<int,pair<int,int>>> adj[1000001];
bool tmp[1000001];
bool vis[1000001];
bool ss = 0;
void cycle(int i,int pr){
    st.push(i);
    if(tmp[i]){
        vector<int> cyc;
        cyc.push_back(i);
        st.pop();
        while(st.top()!=i){
            cyc.push_back(st.top());st.pop();
        }
        for(int j = cyc.size()-1;j>=0;j--)st.push(cyc[j]);
        all.push_back(cyc);
        st.pop();
        ss = 1;
        return;
    }
    tmp[i] = 1;
    for(auto j:adj[i]){
        if(j.second.second==pr)continue;
        cycle(j.first,j.second.second);
        if(ss){
            tmp[i] = 0;
            st.pop();
            return ;
        }
    }
    tmp[i] = 0;
    st.pop();
}
void fil(int i){
    vis[i]=1;
    for(auto j:adj[i]){
        if(!vis[j.first]){
            fil(j.first);
        }
    }
}
long long maxDep[1000005];
long long TreeDim[1000005];
bool ele[1000005];
int sst,node;long long maa;
void ma(int i,int pr,long long dep){
    maxDep[sst] =max(maxDep[sst],dep);
    for(auto j:adj[i]){
        if(j.first==pr||ele[j.first]==1)continue;
        ma(j.first,i,dep+j.second.first);
    }
}
void Dim(int i,int pr,long long dep){
    if(maa<dep){
        maa =dep;
        node = i;
    }
    TreeDim[sst] =max(TreeDim[sst],dep);
    for(auto j:adj[i]){
        if(j.first==pr||ele[j.first]==1)continue;
        Dim(j.first,i,dep+j.second.first);
    }
}
signed main(){
    int n;cin>>n;
    map<pair<int,int>,int>mp;
    for(int i = 1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        mp[{i,a}] = b;
        mp[{a,i}] = b;
        adj[i].push_back({a,{b,i}});
        adj[a].push_back({i,{b,i}});
    }
    for(int i = 1;i<=n;i++){
        if(!vis[i]){
            ss = 0;
            cycle(i,-1);
            fil(i);
        }
    }
    for(auto i:all){
        int len = i.size();
        for(int j = 0;j<i.size();j++){
            ele[i[(j+1)%len]] = 1;
            ele[i[((j-1)%len+len)%len]] = 1;
            sst = i[j];maa = -1,node = i[j];
            ma(i[j],-1,0);
            Dim(node,-1,0);
            maa = -1;
            Dim(node,-1,0);
            ele[i[(j+1)%len]] = 0;
            ele[i[((j-1)%len+len)%len]] = 0;
        }
    }
    long long sum = 0;
    long long cost[1000001];
    for(auto i:all){
        if(i.size()==2){
            long long ans = max(TreeDim[i[0]],TreeDim[i[1]]);
            int e = 0;
            for(auto j:adj[i[0]]){
                if(j.first==i[1])e = max(e,j.second.first);
            }
            ans = max(ans,maxDep[i[0]]+maxDep[i[1]]+e);
            sum+=ans;
            continue;
        }
        long long ans = 0;
        for(auto j:i)ans = max(ans,TreeDim[j]);
        //cout<<ans<<endl;
        multiset<pair<long long,int>> s;
        long long sz = mp[{i[0],i[1]}];
        int len = i.size();
        for(int j = 1;j<i.size();j++){
            //cout<<i[j]<<"hh"<<(-sz)+maxDep[i[j]]<<endl;
            s.insert({(-sz)+maxDep[i[j]],i[j]});
            cost[i[j]] = (-sz)+maxDep[i[j]];
            //cout<<sz<<"\n";
            sz+=mp[{i[j],i[(j+1)%len]}];
        }
        auto it = s.end();it--;
        ans = max(ans,maxDep[i[0]]+sz+(*it).first);
        //cout<<(*it).second<<"\n";
        //cout<<ans<<endl;
        //cout<<i[0]<<" "<<i[1]<<"\n";
        long long global = 0;
        for(int j = i.size()-1;j>=1;j--){
            s.insert({(-global)+maxDep[i[(j+1)%len]],i[(j+1)%len]});
            cost[i[(j+1)%len]] = (-global)+maxDep[i[(j+1)%len]];
            global-=mp[{i[j],i[(j+1)%len]}];
            pair<long long,int> p = {cost[i[j]],i[j]};
            auto it=s.lower_bound(p);
            s.erase(it);
            it = s.end();it--;
            ans = max(ans,(maxDep[i[j]]+sz+(*it).first)+global);
            //cout<<(maxDep[i[j]]+sz+(*it).first)+global<<endl;
        }
        sum+=ans;
        //cout<<sum<<"\n";
    }
    cout<<sum<<endl;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:89:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int j = 0;j<i.size();j++){
      |                       ~^~~~~~~~~
islands.cpp:120:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for(int j = 1;j<i.size();j++){
      |                       ~^~~~~~~~~

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 31556 KB Output is correct
2 Correct 14 ms 31680 KB Output is correct
3 Correct 15 ms 31684 KB Output is correct
4 Correct 15 ms 31556 KB Output is correct
5 Correct 14 ms 31572 KB Output is correct
6 Correct 14 ms 31516 KB Output is correct
7 Correct 15 ms 31556 KB Output is correct
8 Correct 14 ms 31572 KB Output is correct
9 Correct 14 ms 31572 KB Output is correct
10 Correct 16 ms 31564 KB Output is correct
11 Correct 15 ms 31572 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31820 KB Output is correct
2 Correct 16 ms 31784 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 31956 KB Output is correct
2 Correct 22 ms 32724 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 34764 KB Output is correct
2 Correct 87 ms 40728 KB Output is correct
3 Correct 45 ms 35464 KB Output is correct
4 Correct 28 ms 33508 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 44240 KB Output is correct
2 Correct 154 ms 53088 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 71880 KB Output is correct
2 Correct 401 ms 83324 KB Output is correct
3 Correct 476 ms 103344 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 564 ms 108136 KB Output is correct
2 Runtime error 455 ms 131072 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 765 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 729 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -