oj.uz

답안 #59521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
59521 2018-07-22T08:33:38 Z TAMREF Islands (IOI08_islands) C++11
13 / 100
 2000 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];
bool vis[mx];
bool dE[mx];
int n;


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

int dfs_cnt;
int dfs(int x){
    ++dfs_cnt;
    int cyc = 0, tcyc, u;
    vis[x] = 1;
    for(int &e : G[x]){
        if(dE[e]) continue;
        u = E[e].oppo(x);
        if(vis[u]){
            //printf("cycle detected - (%d->%d)\n",x,u);
            cyc = u;
            dE[e] = 1;
            ce.push_back(E[e].w);
        }else{
            dE[e] = 1;
            tcyc = dfs(u);
            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 dfs_st(int x){ //dfs for each subtrees in cycle
    ++dfs_cnt;
    vis[x] = 0;
    int u, w;
    ll ans = 0, ans2 = 0, tmp;
    for(int &e : G[x]){
        u = E[e].oppo(x);
        w = E[e].w;
        if(vis[u] == 1){
            tmp = dfs_st(u) + w;
            if(tmp > ans) ans2 = ans, ans = tmp;
            else ans2 = max(ans2, tmp);
        }
    }
    lans = max(lans, ans + ans2); //local answer in subtree
    return ans;
}

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

    //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];
    }

    ans = max(ans, calc(Vei, ce, Wei));

    //printf("dp result : %lld\n",ans);
    return ans;
}

void input(){
    cin >> 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);
            }
        }
    }
    */
    printf("n = %d, dfs_cnt = %d\n",n,dfs_cnt);
    FILE *fp = fopen(S,"rt");
    ll correct;
    fscanf(fp,"%lld",&correct);
    cout << "answer = " << correct << '\n';
}

int main(){
    //freopen("isl19g.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();
            Weic.clear();
            dfs(i);
            ans += dp_on_cycle();
        }
    }
    cout << ans << '\n';
    //debug("isl19g.out");
}

Compilation message

islands.cpp: In function 'void debug(const char*)':
islands.cpp:172: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
3.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 57 ms 47612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 56 ms 47800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 70 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 28 ms 48120 KB Output is correct
5 Runtime error 60 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 52 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 54 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 57 ms 48288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 65 ms 48288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 51 ms 48300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 62 ms 48300 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 61 ms 48344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 66 ms 48416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 58 ms 49964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 53940 KB Output is correct
2 Runtime error 101 ms 60888 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 69236 KB Output is correct
2 Correct 282 ms 78004 KB Output is correct
3 Correct 358 ms 89040 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 556 ms 102788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1340 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2057 ms 132096 KB Time limit exceeded
2 Halted 0 ms 0 KB -