Submission #872649


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << a << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

typedef long long int ll;
#define int ll
typedef vector<int> vi;
typedef pair<int,int> pii;

const int N = 2e5 + 10;

int n,m, deg[N];
vi adj[N];

bool cyc[N];
vi cycle;

ll res = 0;
int bal[N];
void dfs(int u, int p) {
    bal[u] = 1;
    for (int v : adj[u]) if (!cyc[v] && v != p) {
        dfs(v,u);
        bal[u] -= bal[v];
    }
    if (p != -1) res += abs(bal[u]);
}

void result(ll res) {
    cout << res << '\n';
    exit(0);
}

void find_cycle() {
    vector<int> q;
    forn(u,n) if (deg[u] == 1) q.pb(u);
    while (!q.empty()) {
        int u = q.back(); q.pop_back();
        for (int v : adj[u]) {
            if (--deg[v] == 1) q.pb(v);
        }
    }

    int x;
    forn(u,n) if (deg[u] == 2) {
        x = u;
        break;
    }
    vector<bool> vis(n,false);
    vis[x] = true;
    cycle.pb(x);
    while (1) {
        bool found = false;
        int u = cycle.back();
        for (int v : adj[u]) if (!vis[v] && deg[v] == 2) {
            cycle.pb(v);
            vis[v] = true;
            found = true;
            break;
        }
        if (!found) break;
    }
    for (auto u : cycle) cyc[u] = true;
}

#undef int
int main() {
#define int ll
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    forn(_,m) {
        int u,v; cin >> u >> v;
        u--; v--;
        deg[u]++; deg[v]++;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    if (m == n) {
        find_cycle();

        vi cbal;
        for (int r : cycle) {
            dfs(r,-1);
            cbal.pb(bal[r]);
        }

        if (si(cycle) % 2) {
            ll total = 0;
            forn(i,si(cbal)) {
                if (i%2 == 0) total -= cbal[i]; else total += cbal[i];
            }
            if (total%2) result(-1);
            total /= 2;
            for (auto b : cbal) {
                res += abs(total);
                total = -total-b;
            }
            result(res);
        }
        else {
            vector<ll> cum;
            cum.pb(0);
            forn(i,si(cbal)) {
                if (i%2 == 0) cum.pb(cum.back()-cbal[i]);
                else cum.pb(cum.back()+cbal[i]);
            }
            if (cum.back() != 0) result(-1);

            cum.pop_back(); sort(all(cum));
            ll med = cum[si(cum)/2];
            for (ll x : cum) res += abs(x-med);
            result(res);
        }
    }
    else {
        dfs(0,-1);
        if (bal[0] != 0) result(-1);
        result(res);
    }

    return 0;
}

Submission Info

Submission Time
Task F - Namori
User aurinegro
Language C++14 (GCC 5.4.1)
Score 2200
Code Size 3011 Byte
Status AC
Exec Time 100 ms
Memory 14208 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 1500 / 1500 700 / 700
Status
AC × 4
AC × 20
AC × 66
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
Subtask1 0_00.txt, 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt
Case Name Status Exec Time Memory
0_00.txt AC 11 ms 4992 KB
0_01.txt AC 14 ms 4992 KB
0_02.txt AC 11 ms 4992 KB
0_03.txt AC 12 ms 4992 KB
1_00.txt AC 11 ms 4992 KB
1_01.txt AC 88 ms 14208 KB
1_02.txt AC 74 ms 11384 KB
1_03.txt AC 65 ms 10480 KB
1_04.txt AC 91 ms 12288 KB
1_05.txt AC 84 ms 12032 KB
1_06.txt AC 88 ms 12032 KB
1_07.txt AC 86 ms 11648 KB
1_08.txt AC 86 ms 12416 KB
1_09.txt AC 77 ms 10624 KB
1_10.txt AC 83 ms 10364 KB
1_11.txt AC 82 ms 10240 KB
1_12.txt AC 81 ms 10240 KB
1_13.txt AC 84 ms 10624 KB
1_14.txt AC 83 ms 10240 KB
1_15.txt AC 80 ms 10240 KB
1_16.txt AC 80 ms 10240 KB
1_17.txt AC 82 ms 10240 KB
2_00.txt AC 12 ms 4992 KB
2_01.txt AC 97 ms 12788 KB
2_02.txt AC 84 ms 11884 KB
2_03.txt AC 68 ms 10864 KB
2_04.txt AC 94 ms 12020 KB
2_05.txt AC 99 ms 11960 KB
2_06.txt AC 99 ms 11892 KB
2_07.txt AC 94 ms 12020 KB
2_08.txt AC 97 ms 11968 KB
2_09.txt AC 88 ms 10872 KB
2_10.txt AC 87 ms 10504 KB
2_11.txt AC 96 ms 10376 KB
2_12.txt AC 94 ms 10296 KB
2_13.txt AC 96 ms 11876 KB
2_14.txt AC 98 ms 10552 KB
2_15.txt AC 94 ms 10424 KB
2_16.txt AC 97 ms 10552 KB
2_17.txt AC 92 ms 10292 KB
2_18.txt AC 12 ms 4992 KB
2_19.txt AC 84 ms 11376 KB
2_20.txt AC 74 ms 11252 KB
2_21.txt AC 100 ms 12916 KB
2_22.txt AC 92 ms 11636 KB
2_23.txt AC 95 ms 11548 KB
2_24.txt AC 95 ms 11508 KB
2_25.txt AC 93 ms 11636 KB
2_26.txt AC 94 ms 11580 KB
2_27.txt AC 93 ms 11004 KB
2_28.txt AC 91 ms 10520 KB
2_29.txt AC 91 ms 10444 KB
2_30.txt AC 94 ms 10296 KB
2_31.txt AC 95 ms 11340 KB
2_32.txt AC 94 ms 10424 KB
2_33.txt AC 95 ms 10424 KB
2_34.txt AC 95 ms 10424 KB
2_35.txt AC 96 ms 10296 KB
2_36.txt AC 68 ms 10864 KB
2_37.txt AC 71 ms 10864 KB
2_38.txt AC 70 ms 10864 KB
2_39.txt AC 71 ms 10864 KB
2_40.txt AC 71 ms 10864 KB
2_41.txt AC 68 ms 10864 KB
2_42.txt AC 75 ms 10864 KB
2_43.txt AC 67 ms 10864 KB