제출 #725085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
725085		stevancv	이상적인 도시 (IOI12_city)	C++14	100 / 100	138 ms	19200 KiB

city

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int inf = 1e9;
vector<int> g[N];
ll sz[N], ans;
void Dfs(int s, int e, int n) {
    for (int u : g[s]) {
        if (u == e) continue;
        Dfs(u, s, n);
        sz[s] += sz[u];
    }
    for (int u : g[s]) {
        if (u == e) continue;
        ans += sz[u] * (n - sz[u]);
    }
}
int Resi(int n, int x[], int y[]) {
    map<int, vector<int>> mp;
    map<pair<int, int>, int> id;
    for (int i = 0; i < n; i++) mp[x[i]].push_back(y[i]);
    for (int i = 0; i < n; i++) {
        g[i].clear();
        sz[i] = 0;
    }
    int tsz = 0;
    for (auto z : mp) {
        int ii = z.first;
        auto v = z.second;
        sort(v.begin(), v.end());
        int c = 0;
        for (int i = 0; i < v.size(); i++) {
            if (i == 0 || v[i - 1] + 1 == v[i]) c++;
            else {
                sz[tsz++] = c;
                c = 1;
            }
            id[{ii, v[i]}] = tsz;
        }
        sz[tsz++] = c;
        for (int i = 0; i < v.size(); i++) {
            if (id.find({ii - 1, v[i]}) != id.end()) {
                int o = id[{ii - 1, v[i]}];
                int oo = id[{ii, v[i]}];
                g[o].push_back(oo);
                g[oo].push_back(o);
            }
        }
    }
    for (int i = 0; i < tsz; i++) {
        sort(g[i].begin(), g[i].end());
        g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
    }
    ans = 0;
    Dfs(0, -1, n);
    ans %= inf;
    return ans;
}
int DistanceSum(int n, int x[], int y[]) {return (Resi(n, x, y) + Resi(n, y, x)) % inf;}

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

city.cpp: In function 'int Resi(int, int*, int*)':
city.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~
city.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45