oj.uz

답안 #59551

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
59551 2018-07-22T09:53:22 Z TAMREF Islands (IOI08_islands) C++11
70 / 100
 774 ms 132096 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;

const int mx = 1e6 + 5;

struct Edg{
    int u, v, w;
    inline int oppo(int x){
        return u + v - x;
    }
} E[mx];

vector<int> G[mx];
vector<bool> vis(mx);
vector<bool> vis2(mx);
vector<bool> dE(mx);
int num_cyc = 1; //greater than 1
int n;


vector<int> cv; //cycle vertex
vector<int> ce; //cycle edge weight
vector<ll> Vei, Wei;

int OP;
int dfs(int x){
    int cyc = 0, tcyc;
    vis[x] = 1;
    for(int &e : G[x]){
        if(dE[e]) continue;
        OP = E[e].oppo(x);
        if(vis[OP]){
            //printf("cycle detected - (%d->%d)\n",x,u);
            cyc = OP;
            dE[e] = 1;
            ce.push_back(E[e].w);
        }else{
            dE[e] = 1;
            tcyc = dfs(OP);
            cyc |= tcyc;
            if(tcyc){
                ce.push_back(E[e].w);
            }
        }
    }
    if(cyc){
        //printf("push %d in cv\n",x);
        cv.push_back(x);
    }
    if(cyc == x){
        //printf("stopping cycle in %d\n",x);
        cyc = 0;
    }
    return cyc;
}

ll lans;
ll ans[mx], ans2[mx];
void dfs_st(int x){ //dfs for each subtrees in cycle
    vis2[x] = 1;
    for(int &e : G[x]){
        OP = E[e].oppo(x);
        if(!vis2[OP]){
            dfs_st(OP);
            ans2[x] = max(ans2[x], ans[E[e].oppo(x)] + E[e].w);
            if(ans2[x] > ans[x]){
                ans[x] ^= ans2[x];
                ans2[x] ^= ans[x];
                ans[x] ^= ans2[x];
            }
        }
    }
    lans = max(lans, ans[x] + ans2[x]); //local answer in subtree
}

inline void BackInsert(deque<pli>& d, pli p){
    while(!d.empty() && d.back() <= p) d.pop_back();
    d.push_back(p);
}

inline void OldPop(deque<pli>& d, int k){
    while(!d.empty() && d.front().second < k) d.pop_front();
}

ll calc(vector<ll>& Vw, vector<int>& E, vector<ll>& sE){
    deque<pli> dq;
    int m = E.size();
    ll lsum = E[0];
    ll ret = 0;

    for(int i = 1; i < m; i++){
        BackInsert(dq, pli(Vw[i] + sE[i], i));
        lsum += E[i];
    }
    for(int i = 0; i < m; i++){
        OldPop(dq, i+1);
        ret = max(ret, Vw[i] - sE[i] + dq.front().first);
        BackInsert(dq, pli(Vw[i] + lsum + sE[i], i+m));
    }
    dq.clear();
    dq.shrink_to_fit();
    return ret;
}

ll dp_on_cycle(){
    int C = cv.size();
    ll lsum = 0;
    ll ret = 0;
    //give cycle-vertices their own number
    rotate(ce.begin(),ce.begin()+1,ce.end()); //f**k
    for(int i = 0; i < C; i++){
        vis2[cv[i]] = 1;
        //printf("vertex : %d, clockwise - edge : %d\n",cv[i],ce[i]);
    }
    //clockwise
    for(int i = 0; i < C; i++){
        dfs_st(cv[i]);
        Vei.push_back( ans[cv[i]] );
        Wei.push_back( lsum );
        lsum += ce[i];
    }
    ret = max(ret, calc(Vei, ce, Wei));

    //inclockwise - reversing all the vectors
    lsum = 0;
    reverse(cv.begin(),cv.end());
    reverse(Vei.begin(),Vei.end());

    reverse(ce.begin(), ce.end() - 1);

    for(int i = 0; i < C; i++){
        //printf("vertex : %d, Inc ew : %d\n",cv[i],ce[i]);
        Wei[i] = lsum;
        lsum += ce[i];
    }

    ret = max(ret, calc(Vei, ce, Wei));
    ret = max(ret, lans);
    //printf("dp result : %lld\n",ans);
    return ret;
}

void input(){
    cin >> n;
    cv.reserve(n);
    ce.reserve(n);
    Vei.reserve(n);
    Wei.reserve(n);
    for(int i = 1; i <= n; i++){
        cin >> E[i].v >> E[i].w;
        E[i].u = i;
        G[i].push_back(i);
        G[E[i].v].push_back(i);
    }
}

void debug(const char* S){
    /*
    for(int i = 1; i <= n; i++){
        if(G[i].size() > 1){
            //printf("deg[%d] = %d\n",i,G[i].size());
            for(int &e : G[i]){
                if(E[e].w > 90000000)
                    //printf("(%d, %d)\n",E[e].oppo(i),E[e].w);
            }
        }
    }
    */
    FILE *fp = fopen(S,"rt");
    ll correct;
    fscanf(fp,"%lld",&correct);
    printf("answer = %lld\n",correct);
}

int main(){
    //freopen("isl10.in","rt",stdin);
    ios_base::sync_with_stdio(false);cin.tie(0);
    ll ans = 0;
    input();
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            cv.clear();
            ce.clear();
            Wei.clear();
            Vei.clear();
            dfs(i);
            lans = 0;
            ans += dp_on_cycle();
        }
    }
    cout << ans << '\n';
    //debug("isl10.out");
}

Compilation message

islands.cpp: In function 'void debug(const char*)':
islands.cpp:175:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fp,"%lld",&correct);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 24184 KB Output is correct
2 Correct 24 ms 24304 KB Output is correct
3 Correct 26 ms 24304 KB Output is correct
4 Correct 25 ms 24304 KB Output is correct
5 Correct 29 ms 24304 KB Output is correct
6 Correct 29 ms 24468 KB Output is correct
7 Correct 27 ms 24468 KB Output is correct
8 Correct 29 ms 24492 KB Output is correct
9 Correct 27 ms 24492 KB Output is correct
10 Correct 25 ms 24500 KB Output is correct
11 Correct 27 ms 24500 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 24580 KB Output is correct
2 Correct 26 ms 24640 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 24640 KB Output is correct
2 Correct 32 ms 25048 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 25952 KB Output is correct
2 Correct 63 ms 28572 KB Output is correct
3 Correct 54 ms 28572 KB Output is correct
4 Correct 34 ms 28572 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 31000 KB Output is correct
2 Correct 111 ms 34504 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 43800 KB Output is correct
2 Correct 191 ms 50064 KB Output is correct
3 Correct 222 ms 63708 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 64912 KB Output is correct
2 Correct 333 ms 93732 KB Output is correct
3 Correct 322 ms 102028 KB Output is correct
4 Runtime error 402 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.

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 481 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 774 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 -