oj.uz

Submission #1057130

# Submission time Handle Problem Language Result Execution time Memory
1057130 2024-08-13T14:25:55 Z Thanhs Logičari (COCI21_logicari) C++14
0 / 110
 1000 ms 20872 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define all(x) x.begin(), x.end()
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 1e5 + 5;
const int inf = 1e9;

vector<int> g[NM];
int n, dp[NM][2][2], deg[NM], val[NM][3], f[NM][2][2], ans;
bool vis[NM];
stack<int> st;
vector<int> a;

void calc(int u)
{
    int d01 = inf, d11 = inf;
    bool b = 0;
    for (int v : g[u])
        if (vis[v])
        {
            b = 1;
            dp[u][0][0] += dp[v][0][1];
            dp[u][1][0] += dp[v][0][0];
            setmin(d01, dp[v][1][1] - dp[v][0][1]);
            setmin(d11, dp[v][1][0] - dp[v][0][0]);
        }
    dp[u][1][0]++;
    dp[u][0][1] = dp[u][0][0] + d01;
    dp[u][1][1] = dp[u][1][0] + d11;
}

void dfs(int u, int p, int pp)
{
    a.push_back(u);
    for (int v : g[u])
        if (v != p && v != pp && !vis[v])
        {
            dfs(v, u, pp);
            break;
        }
    bool b = 0;
    calc(u);
}

int cost(int x)
{
    return val[x][1] + val[x - 1][2] + val[x - 2][2] + val[x - 3][1];
}

void tinh(bool s1, bool s2)
{
    // cout << s1 << ' ' << s2 << endl;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            f[1][i][j] = inf;
    f[1][s1][s2] = dp[a[1]][s1][s2];
    for (int i = 2; i <= n; i++)
    {
        int u = a[i];
        f[i][0][0] = dp[u][0][0] + f[i - 1][0][1];
        f[i][1][0] = dp[u][1][0] + f[i - 1][0][0];
        f[i][0][1] = min(dp[u][0][1] + f[i - 1][0][1], dp[u][0][0] + f[i - 1][1][1]);
        f[i][1][1] = min(dp[u][1][1] + f[i - 1][1][0], dp[u][1][0] + f[i - 1][1][0]);
        // for (int j = 0; j < 2; j++)
        //     for (int k = 0; k < 2; k++)
        //         cout << i << ' ' << j << ' ' << k << ' ' << f[i][j][k] << endl;
    }
    // cout << f[n][0][!s1] << endl;
    // cout << endl;
    setmin(ans, f[n][0][!s1]);
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    for (int i = 1; i <= n; i++)
        if (deg[i] == 1)
            st.push(i);
    while (!st.empty())
    {
        int u = st.top();
        st.pop();
        vis[u] = 1;
        calc(u);
        for (int v : g[u])
            if (!vis[v])
            {
                deg[v]--;
                if(deg[v] == 1)
                    st.push(v);
            }
    }
    a.push_back(0);
    for (int i = 1; i <= n; i++)
        if (!vis[i])
        {
            dfs(i, 0, i);
            break;
        }
    n = a.size() - 1;
    ans = inf;
    for (int _ = 1; _ < n; _++)
    {
        for (int s1 = 0; s1 < 2; s1++)
            for (int s2 = 0; s2 < 2; s2++)
                tinh(s1, s2);
        for (int i = 0; i < n; i++)
            a[i] = a[i + 1];
        a[n] = a[0];
    }
    cout << (ans < inf ? ans : -1);
}

signed main()
{
    fastIO
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int tc = 1;
    // cin >> tc;
    while (tc--)
        solve();
}

Compilation message

Main.cpp: In function 'void calc(long long int)':
Main.cpp:32:10: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   32 |     bool b = 0;
      |          ^
Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:56:10: warning: unused variable 'b' [-Wunused-variable]
   56 |     bool b = 0;
      |          ^
Main.cpp: In function 'int main()':
Main.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Execution timed out 1098 ms 20872 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Incorrect 1 ms 5724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Incorrect 1 ms 5724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Execution timed out 1098 ms 20872 KB Time limit exceeded
6 Halted 0 ms 0 KB -