제출 #982582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982582		JooDdae	전압 (JOI14_voltage)	C++17	100 / 100	83 ms	22680 KiB

voltage

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

int n, m, col[100100], chk[200200];
vector<array<int, 2>> v[100100], odd, even;

int in[100100], out[100100], t[200200], cnt;

void dfs(int u, int p, int pid, int c) {
    col[u] = c, in[u] = ++cnt;

    for(auto [x, id] : v[u]) if(!chk[id]) {
        chk[id] = 1;
        if(col[x] == -1) {
            dfs(x, u, id, c^1);
            continue;
        }

        if(col[x] != c) even.push_back({u, x});
        else odd.push_back({u, x});
    }

    out[u] = ++cnt;
}

void update(int b, int c) {
    while(b <= 2*n) t[b] += c, b += b & -b;
}

int find(int b) {
    int re = 0;
    while(b) re += t[b], b -= b & -b;
    return re;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        int x, y; cin >> x >> y;
        v[x].push_back({y, i}), v[y].push_back({x, i});
    }
    memset(col, -1, sizeof col);
    for(int i=1;i<=n;i++) if(!in[i]) dfs(i, 0, 0, 0), update(in[i], 3*m), update(in[i]+1, -3*m);

    for(auto [x, y] : even) update(in[y]+1, -1), update(in[x]+1, 1);
    for(auto [x, y] : odd) update(in[y]+1, 1), update(in[x]+1, -1);

    int cnt = 0;
    for(int i=2;i<=n;i++) if(find(in[i])-find(out[i]) == odd.size()) cnt++;
    cout << cnt + (odd.size() == 1);
}

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

voltage.cpp: In function 'int main()':
voltage.cpp:51:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=2;i<=n;i++) if(find(in[i])-find(out[i]) == odd.size()) cnt++;
      |                              ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45