Submission #539496

#	Time	Username	Problem	Language	Result	Execution time	Memory
539496		joshualiu555	Forensic (NOI12_forensic)	C++17	25 / 25	3 ms	1508 KiB

forensic

/*
  _____                                     _        _
 / ____|                                   | |      | |
| |  __ _ __ __ _ ___ ___ _   _ _ __   ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
 \_____|_|  \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
                           __/ | |
                          |___/|_|
*/

#pragma gcc target ("avx2")
#pragma gcc optimization ("O3")
#pragma gcc optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using segset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, x, n) for (int i = x; i <= n; i++)
#define F0R(i, x, n) for (int i = x; i >= n; i--)
#define TRAV(it, x) for (auto it = x.begin(); it != x.end(); it++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
//#define f first
//#define s second
#define sz size
#define pob pop_back
#define pf push_front
#define pb push_back
#define ins insert
#define mp make_pair
#define rz resize
#define asg assign
#define rev reverse
#define lb lower_bound
#define ub upper_bound
// fill for 1
// 0x3f3f3f3f for 1e9
#define mem(a, x) memset(a, x, sizeof(a))
#define HEX 0x3f3f3f3f

using ll = long long;
const int INF = 2e5 + 5;
const int MOD = 1e9 + 7;
// DLRU
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, -1, 1, 0};

int n, a[INF];

int visited[INF], dp[INF];
bool cycle = false;

int ans1 = 0;
void dfs1(int node) {
    if (visited[node] == 1) {
        cycle = true;
        return;
    }
    if (node == -1) return;
    visited[node] = 1;
    ans1++;
    dp[node] = 0;
    dfs1(a[node]);
}

int dfs2(int node) {
    // end linked list
    if (node == -1) return 0;
    // cycles back to 0
    if (node == 0) return -1e9;
    // converges into a cycle in the main path
    if (visited[node] == 1 && cycle) return -1e9;
    // converges into a path
    if (dp[node] != -1) return dp[node];
    // converges into a cycle in a new path
    if (visited[node] == 2) return -1e9;
    // increase length of current path
    visited[node] = 2;
    dp[node] = dfs2(a[node]) + 1;
    return dp[node];
}

//10 2 5 4 4 -1 1 -1 3 0 8

int main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(0);

    mem(dp, -1);

    cin >> n;
    FOR(i, 0, n - 1) cin >> a[i];

    if (a[0] == 0) {
        cout << 1 << '\n';
        return 0;
    }

    dfs1(0);

    int ans2 = 0;
    FOR(i, 0, n - 1) {
        if (!visited[i]) {
            ans2 = max(ans2, dfs2(i));
        }
    }

    cout << ans1 + ans2 << '\n';

    return 0;
}

/*
 * corner case: if 0 goes to 0, just output 1
 *
 * the final linked list must end at -1
 * therefore, you can't have a cycle
 *
 * x = last node in 0 path
 * y = second to last node in 0 path
 *
 * case 1: connect x to a new path
 * case 2: connect y to a path that ends at x
 * case 3: 0 path is a cycle so connect y to
 * the longest path
 *
 * find the length of the 0 path
 * find the length of all -1 chains
 * and choose the longest one
 * add these two lengths together
*/

//

Compilation message (stderr)

forensic.cpp:12: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
   12 | #pragma gcc target ("avx2")
      | 
forensic.cpp:13: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   13 | #pragma gcc optimization ("O3")
      | 
forensic.cpp:14: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   14 | #pragma gcc optimization ("unroll-loops")
      |

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 10 / 10