제출 #474477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
474477		Valaki2	Traffic (IOI10_traffic)	C++14	100 / 100	1222 ms	167860 KiB

traffic

#include "traffic.h"

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

#define pb push_back

const int maxn = 1e6;

struct edge {
    int to, id, cong;
    edge(int to_, int id_, int cong_) : to(to_), id(id_), cong(cong_) {}
};

int n, sum;
vector<edge> g[maxn + 1];
int val[maxn + 1];
bool vis[maxn + 1];

int dfs(int x, int id) {
    vis[x] = true;
    int res = val[x];
    int cur_ind = 0;
    for(int i = 0; i < g[x].size(); ++i) {
        if(g[x][i].id == id) {
            cur_ind = i;
        } else {
            int temp = dfs(g[x][i].to, g[x][i].id);
            res += temp;
            g[x][i].cong = temp;
        }
    }
    if(x != 1) g[x][cur_ind].cong = sum - res;
    return res;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    n = N;
    for(int i = 0; i < n; ++i) {
        val[i + 1] = pp[i];
        sum += val[i + 1];
    }
    for(int i = 0; i < n - 1; ++i) {
        g[S[i] + 1].pb(edge(D[i] + 1, i + 1, 0));
        g[D[i] + 1].pb(edge(S[i] + 1, i + 1, 0));
    }
    dfs(1, 0);
    /*for(int i = 1; i <= n; ++i) {
        cout << i << ": " << val[i] << ";\n";
        for(edge x : g[i]) cout << x.to << " " << x.id << " " << x.cong << "\n";
        cout << "\n";
    }*/
    int ans = 1, best = INT_MAX;
    for(int i = 1; i <= n; ++i) {
        int cur = 0;
        for(edge e : g[i]) {
            cur = max(cur, e.cong);
        }
        if(cur < best) {
            best = cur;
            ans = i;
        }
    }
    return ans - 1;
}

컴파일 시 표준 에러 (stderr) 메시지

traffic.cpp: In function 'int dfs(int, int)':
traffic.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0; i < g[x].size(); ++i) {
      |                    ~~^~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25