QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#632621#9230. Routing K-CodesFDUdululuCompile Error//C++207.5kb2024-10-12 13:40:432024-10-12 13:40:44

Judging History

你现在查看的是最新测评结果

  • [2024-10-12 13:40:44]
  • 评测
查看
  • [2024-10-12 13:40:43]
  • 提交

answer

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

const int N = 2e5 + 5;
const ll inf = 9e18;

int n, m;
pair<int, int> e[N];
vector<int> son[N];
int deg[N];
ll k[N], b[N], ans;
int u[N], v[N], w[N];
int dep[N], maxn[N], mexn[N], dia;

void dfs1(int x, int fa) {
    dep[x] = dep[fa] + 1;
    k[x] = 1;
    b[x] = 0;
    maxn[x] = mexn[x] = dep[x];
    for (auto y : son[x]) {
        if (y == fa)
            continue;
        dfs1(y, x);
        if (v[x])
            w[x] = y;
        else if (u[x])
            v[x] = y;
        else
            u[x] = y;

        if (maxn[y] >= maxn[x]) {
            mexn[x] = maxn[x];
            maxn[x] = maxn[y];
        } else if (maxn[y] >= mexn[x])
            mexn[x] = maxn[y];
    }
    dia = max(dia, maxn[x] - dep[x] + mexn[x] - dep[x] + 1);

    if (k[u[x]] < k[v[x]])
        swap(u[x], v[x]);
    if (k[u[x]] < k[w[x]])
        swap(u[x], w[x]);
    int o = u[x], p = v[x], q = w[x];
    k[x] += 2ll * (k[o] + k[p] + k[q]);
    b[x] += (b[o] + b[p] + b[q]) + (k[p] + k[q]);
    // cout<<"? "<<x<<" "<<k[x]<<" "<<b[x]<<"\n";
}

void calc(int x, int y) {
    int u = 0, v = 0;
    for (auto z : son[x]) {
        if (z == y)
            continue;
        if (u)
            v = z;
        else
            u = z;
    }
    k[x] = 1 + 2ll * (k[u] + k[v]);
    b[x] = (b[u] + b[v]) + min(k[u], k[v]);
}

void dfs2(int x, int fa, int depfa) {
    // cout<<"? "<<x<<" "<<k[x]<<" "<<b[x]<<" "<<u[x]<<"\n";

    for (auto y : son[x]) {
        if (y == fa)
            continue;

        ll old_k_x = k[x], old_b_x = b[x];
        calc(x, y);

        int len = 0;
        if (maxn[x] == maxn[y])
            len = mexn[x];
        else
            len = maxn[x];
        len = len - dep[x] + 1;
        len = max(len, depfa + 1);

        ll old_k_y = k[y], old_b_y = b[y];
        // int o = x, p = u[y], q = v[y];
        // if (k[o] < k[p])
        //     swap(o, p);
        // if (k[o] < k[q])
        //     swap(o, q);
        // k[y] = 1 + 2ll * (k[o] + k[p] + k[q]);
        // b[y] = (b[o] + b[p] + b[q]) + (k[p] + k[q]);

        // cout<<"! "<<y<<" "<<k[y]<<" "<<b[y]<<"|"<<o<<" "<<k[o]<<" "<<b[o]<<"|";

        // cout<<ans<<"\n";

        if (deg[y] == 1) {
            if (len - 1 < 32) {
                calc(y, -1);
                ans = min(ans, k[x] + b[x]);
            }
        } else if (deg[y] == 2) {
            if (len < 32) {
                calc(y, -1);
                ans = min(ans, k[y] + b[y]);
            }
        }

        dfs2(y, x, len);

        k[y] = old_k_y, b[y] = old_b_y;
        k[x] = old_k_x, b[x] = old_b_x;
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        e[i] = make_pair(x, y);
    }

    if (m >= n) {
        cout << "NIE\n";
        return;
    }
    for (int i = 1; i < n; i++) {
        int x = e[i].first;
        int y = e[i].second;
        son[x].push_back(y);
        son[y].push_back(x);
        deg[x]++;
        deg[y]++;
    }

    for (int i = 1; i <= n; i++) {
        if (deg[i] > 3) {
            cout << "NIE\n";
            return;
        }
    }

    dfs1(1, 0);

    if (dia / 2 >= 32) {
        cout << "NIE\n";
        return;
    }

    ans = inf;
    if (deg[1] == 1) {
        if (maxn[1] - 2 < 32)
            ans = min(ans, k[u[1]] + b[u[1]]);
    } else if (deg[1] == 2) {
        if (maxn[1] - 1 < 32)
            ans = min(ans, k[1] + b[1]);
    }

    dfs2(1, 0, 0);
    if (ans == inf) {
        cout << "NIE\n";
        return;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n = 1;
    // cin>>n;
    while (n--)
        solve();
    return 0;
}

int n, m;
pair<int, int> e[N];
vector<int> son[N];
int deg[N];
ll k[N], b[N], ans;
int u[N], v[N], w[N];
int dep[N], maxn[N], mexn[N], dia;

void dfs1(int x, int fa) {
    dep[x] = dep[fa] + 1;
    k[x] = 1;
    b[x] = 0;
    maxn[x] = mexn[x] = dep[x];
    for (auto y : son[x]) {
        if (y == fa)
            continue;
        dfs1(y, x);
        if (v[x])
            w[x] = y;
        else if (u[x])
            v[x] = y;
        else
            u[x] = y;

        if (maxn[y] >= maxn[x]) {
            mexn[x] = maxn[x];
            maxn[x] = maxn[y];
        } else if (maxn[y] >= mexn[x])
            mexn[x] = maxn[y];
    }
    dia = max(dia, maxn[x] - dep[x] + mexn[x] - dep[x] + 1);

    if (k[u[x]] < k[v[x]])
        swap(u[x], v[x]);
    if (k[u[x]] < k[w[x]])
        swap(u[x], w[x]);

    int o = u[x], p = v[x], q = w[x];
    k[x] += 2ll * (k[o] + k[p] + k[q]);
    b[x] += (b[o] + b[p] + b[q]) + (k[p] + k[q]);
    // if(!(p+q)) b[x]+=1;
    // cout<<"? "<<x<<" "<<k[x]<<" "<<b[x]<<"\n";
}

void dfs2(int x, int fa, int depfa) {
    // cout<<"? "<<x<<" "<<k[x]<<" "<<b[x]<<" "<<u[x]<<"\n";

    for (auto y : son[x]) {
        if (y == fa)
            continue;

        ll old_k_x = k[x], old_b_x = b[x];

        k[x] -= 2ll * k[y], b[x] -= b[y];
        if (y == u[x]) {
            if (w[x])
                b[x] -= max(k[v[x]], k[w[x]]);
            else
                b[x] -= k[v[x]];
        } else {
            b[x] -= k[y];
        }
        int len;
        if (maxn[x] == maxn[y])
            len = mexn[x];
        else
            len = maxn[x];
        len = len - dep[x] + 1;
        len = max(len, depfa + 1);

        // cout<<"# "<<k[x]<<" "<<k[y]<<"\n";

        ll old_k_y = k[y], old_b_y = b[y];

        int o = x, p = u[y], q = v[y];
        if (k[o] < k[p])
            swap(o, p);
        if (k[o] < k[q])
            swap(o, q);
        k[y] = 1 + 2ll * (k[o] + k[p] + k[q]);
        b[y] = (b[o] + b[p] + b[q]) + (k[p] + k[q]);
        // if(!(p+q)) b[y]+=1;

        // cout<<"! "<<y<<" "<<k[y]<<" "<<b[y]<<"|"<<o<<" "<<k[o]<<" "<<b[o]<<"|";

        // cout<<ans<<"\n";

        if (deg[y] == 1) {
            if (len - 1 < 32)
                ans = min(ans, k[o] + b[o]);
        } else if (deg[y] == 2) {
            if (len < 32)
                ans = min(ans, k[y] + b[y]);
        }

        dfs2(y, x, len);

        k[y] = old_k_y, b[y] = old_b_y;
        k[x] = old_k_x, b[x] = old_b_x;
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        e[i] = make_pair(x, y);
    }

    if (m >= n) {
        cout << "NIE\n";
        return;
    }
    for (int i = 1; i < n; i++) {
        int x = e[i].first;
        int y = e[i].second;
        son[x].push_back(y);
        son[y].push_back(x);
        deg[x]++;
        deg[y]++;
    }

    for (int i = 1; i <= n; i++) {
        if (deg[i] > 3) {
            cout << "NIE\n";
            return;
        }
    }

    dfs1(1, 0);

    if (dia / 2 >= 32) {
        cout << "NIE\n";
        return;
    }

    ans = inf;
    if (deg[1] == 1) {
        if (maxn[1] - 2 < 32)
            ans = min(ans, k[u[1]] + b[u[1]]);
    } else if (deg[1] == 2) {
        if (maxn[1] - 1 < 32)
            ans = min(ans, k[1] + b[1]);
    }

    dfs2(1, 0, 0);
    if (ans == inf) {
        cout << "NIE\n";
        return;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n = 1;
    // cin>>n;
    while (n--)
        solve();
    return 0;
}
Source code, Language: C++20

Details 

answer.code:177:5: error: redefinition of ‘int n’
  177 | int n, m;
      |     ^
answer.code:8:5: note: ‘int n’ previously declared here
    8 | int n, m;
      |     ^
answer.code:177:8: error: redefinition of ‘int m’
  177 | int n, m;
      |        ^
answer.code:8:8: note: ‘int m’ previously declared here
    8 | int n, m;
      |        ^
answer.code:178:16: error: redefinition of ‘std::pair<int, int> e [200005]’
  178 | pair<int, int> e[N];
      |                ^
answer.code:9:16: note: ‘std::pair<int, int> e [200005]’ previously defined here
    9 | pair<int, int> e[N];
      |                ^
answer.code:179:13: error: redefinition of ‘std::vector<int> son [200005]’
  179 | vector<int> son[N];
      |             ^~~
answer.code:10:13: note: ‘std::vector<int> son [200005]’ previously defined here
   10 | vector<int> son[N];
      |             ^~~
answer.code:180:5: error: redefinition of ‘int deg [200005]’
  180 | int deg[N];
      |     ^~~
answer.code:11:5: note: ‘int deg [200005]’ previously declared here
   11 | int deg[N];
      |     ^~~
answer.code:181:4: error: redefinition of ‘ll k [200005]’
  181 | ll k[N], b[N], ans;
      |    ^
answer.code:12:4: note: ‘ll k [200005]’ previously declared here
   12 | ll k[N], b[N], ans;
      |    ^
answer.code:181:10: error: redefinition of ‘ll b [200005]’
  181 | ll k[N], b[N], ans;
      |          ^
answer.code:12:10: note: ‘ll b [200005]’ previously declared here
   12 | ll k[N], b[N], ans;
      |          ^
answer.code:181:16: error: redefinition of ‘ll ans’
  181 | ll k[N], b[N], ans;
      |                ^~~
answer.code:12:16: note: ‘ll ans’ previously declared here
   12 | ll k[N], b[N], ans;
      |                ^~~
answer.code:182:5: error: redefinition of ‘int u [200005]’
  182 | int u[N], v[N], w[N];
      |     ^
answer.code:13:5: note: ‘int u [200005]’ previously declared here
   13 | int u[N], v[N], w[N];
      |     ^
answer.code:182:11: error: redefinition of ‘int v [200005]’
  182 | int u[N], v[N], w[N];
      |           ^
answer.code:13:11: note: ‘int v [200005]’ previously declared here
   13 | int u[N], v[N], w[N];
      |           ^
answer.code:182:17: error: redefinition of ‘int w [200005]’
  182 | int u[N], v[N], w[N];
      |                 ^
answer.code:13:17: note: ‘int w [200005]’ previously declared here
   13 | int u[N], v[N], w[N];
      |                 ^
answer.code:183:5: error: redefinition of ‘int dep [200005]’
  183 | int dep[N], maxn[N], mexn[N], dia;
      |     ^~~
answer.code:14:5: note: ‘int dep [200005]’ previously declared here
   14 | int dep[N], maxn[N], mexn[N], dia;
      |     ^~~
answer.code:183:13: error: redefinition of ‘int maxn [200005]’
  183 | int dep[N], maxn[N], mexn[N], dia;
      |             ^~~~
answer.code:14:13: note: ‘int maxn [200005]’ previously declared here
   14 | int dep[N], maxn[N], mexn[N], dia;
      |             ^~~~
answer.code:183:22: error: redefinition of ‘int mexn [200005]’
  183 | int dep[N], maxn[N], mexn[N], dia;
      |                      ^~~~
answer.code:14:22: note: ‘int mexn [200005]’ previously declared here
   14 | int dep[N], maxn[N], mexn[N], dia;
      |                      ^~~~
answer.code:183:31: error: redefinition of ‘int dia’
  183 | int dep[N], maxn[N], mexn[N], dia;
      |                               ^~~
answer.code:14:31: note: ‘int dia’ previously declared here
   14 | int dep[N], maxn[N], mexn[N], dia;
      |                               ^~~
answer.code:185:6: error: redefinition of ‘void dfs1(int, int)’
  185 | void dfs1(int x, int fa) {
      |      ^~~~
answer.code:16:6: note: ‘void dfs1(int, int)’ previously defined here
   16 | void dfs1(int x, int fa) {
      |      ^~~~
answer.code:221:6: error: redefinition of ‘void dfs2(int, int, int)’
  221 | void dfs2(int x, int fa, int depfa) {
      |      ^~~~
answer.code:64:6: note: ‘void dfs2(int, int, int)’ previously defined here
   64 | void dfs2(int x, int fa, int depfa) {
      |      ^~~~
answer.code:279:6: error: redefinition of ‘void solve()’
  279 | void solve() {
      |      ^~~~~
answer.code:114:6: note: ‘void solve()’ previously defined here
  114 | void solve() {
      |      ^~~~~
answer.code:331:5: error: redefinition of ‘int main()’
  331 | int main() {
      |     ^~~~
answer.code:166:5: note: ‘int main()’ previously defined here
  166 | int main() {
      |     ^~~~
English 繁體中文 简体中文

Server Time: 2024-12-05 03:29:59 | OpenSource Project