oj.uz

Submission #84721

# Submission time Handle Problem Language Result Execution time Memory
84721 2018-11-17T02:51:53 Z updown1 Islands (IOI08_islands) C++17
27 / 100
 602 ms 132096 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
const int MAXN=1000000;
///500,000,000
int N, comp[MAXN], cat, nonn[MAXN], siz[MAXN], st[MAXN], out, ns[MAXN], nd[MAXN], pre1[MAXN], pre2[MAXN], suf1[MAXN], suf2[MAXN];
bool vis[MAXN], cyc[MAXN];
queue<int> next1;
vector<pair<int, int> > adj[MAXN]; /// (node, cost)

void go(int at) {
    if (comp[at] != -1) return;
    comp[at] = cat;
    for (auto i: adj[at]) go(i.a);
}
void calc_size(int at) {
    if (vis[at]) return;
    vis[at] = true;
    if (adj[at].size() == 1) return;
    for (auto i: adj[at]) if (!cyc[i.a]) {
        calc_size(i.a);
        siz[at] = max(siz[at], i.b+siz[i.a]);
    }
}
int solve (int x) {
    int ret = 0;
    int loc = 0; int at = st[x];
    //w<< "comp" s x <<e;
    while (at != st[x] || loc == 0) {
        //w<< at+1<<e;
        ns[loc] = siz[at];
        vis[at] = true;
        bool found = false;
        for (auto i: adj[at]) if (!vis[i.a]) {
            nd[loc] = i.b;
            at = i.a;
            found = true;
            break;
        }
        if (!found) {
            vis[st[x]] = false;
            for (auto i: adj[at]) if (!vis[i.a]) {
                nd[loc] = i.b;
                at = i.a;
            }
        }
        loc++;
    }
    if (loc == 1) return 0;
    //For (i, 0, loc) w<< ns[i] s nd[i]<<e;
    pre1[0] = ns[0];
    int curr = 0;
    For (i, 1, loc) {
        curr += nd[i-1];
        pre1[i] = max(pre1[i-1], curr+ns[i]);
    }
    //For (i, 0, loc) w<< "pre1" s i c pre1[i]<<e;
    suf1[0] = ns[0];
    suf1[loc-1] = nd[loc-1] + ns[loc-1];
    curr = nd[loc-1];
    for (int i=loc-2; i>=1; i--) {
        curr += nd[i];
        suf1[i] = max(suf1[i+1], curr+ns[i]);
    }
    //For (i, 0, loc) w<< "suf1" s i c suf1[i]<<e;
    For (i, 0, loc) ret = max(ret, pre1[i] + suf1[(i+1)%loc]);
    //w<< "from pass 1, ret =" s ret<<e;
    pre2[0] = ns[0];
    For (i, 1, loc) pre2[i] = max(pre2[i-1]+nd[i-1], ns[i]);
    //For (i, 0, loc) w<< "pre2" s i c pre2[i]<<e;
    suf2[loc-1] = ns[loc-1];
    for (int i=loc-2; i>=0; i--) suf2[i] = max(suf2[i+1]+nd[i], ns[i]);
    //For (i, 0, loc) w<< "suf2" s i c suf2[i]<<e;
    For (i, 0, loc) ret = max(ret, pre2[i]+suf2[i]);
    //w<< "after pass 2, ret =" s ret<<e;
    return ret;
}

main() {
    //ifstream cin("test.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    ffi {cyc[i] = true; comp[i] = -1; int b, d; cin >> b >> d; b--; adj[i].pb(mp(b, d)); adj[b].pb(mp(i, d));}
    ffi if (comp[i] == -1) {go(i); cat++;}
    ffi if (adj[i].size() == 1) next1.push(i);
    while (!next1.empty()) {
        int at = next1.front(); next1.pop();
        if (!cyc[at]) continue;
        if (nonn[at] == adj[at].size()-1) {
            cyc[at] = false;
            for (auto i: adj[at]) {
                nonn[i.a]++;
                if (cyc[i.a]) next1.push(i.a);
            }
        }
    }
    //ffi w<< i+1 c cyc[i]<<e;
    ffi if (cyc[i]) {st[comp[i]] = i; calc_size(i);}
    //ffi if (cyc[i]) w<< i+1 c siz[i]<<e;
    ffi {
        vis[i] = false;
        if (!cyc[i]) vis[i] = true;
    }
    //solve(1);
    For (i, 0, cat) out += solve(i); w<< out<<e;
}

Compilation message

islands.cpp:92:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
islands.cpp: In function 'int main()':
islands.cpp:102:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (nonn[at] == adj[at].size()-1) {
             ~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23928 KB Output is correct
2 Incorrect 28 ms 24056 KB Output isn't correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 26 ms 24092 KB Output is correct
5 Correct 24 ms 24116 KB Output is correct
6 Correct 23 ms 24120 KB Output is correct
7 Correct 24 ms 24216 KB Output is correct
8 Incorrect 23 ms 24400 KB Output isn't correct
9 Correct 29 ms 24400 KB Output is correct
10 Incorrect 24 ms 24400 KB Output isn't correct
11 Correct 26 ms 24400 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24404 KB Output is correct
2 Correct 24 ms 24432 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 24468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 25904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 30852 KB Output is correct
2 Incorrect 72 ms 35344 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 46556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 65676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 430 ms 115028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 602 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -