제출 #973143

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
973143	2024-05-01 14:28:00	12345678	이상적인 도시 (IOI12_city)	C++17	100 / 100	129 ms	23788 KiB

city

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5, mod=1e9;
ll n, t, sz[nx], dp[nx], res;
set<ll> d[nx];
map<ll, vector<ll>> mpx, mpy;
map<pair<ll, ll>, ll> mp;
void dfs(int u, int p)
{
    dp[u]=sz[u];
    for (auto v:d[u]) if (v!=p) dfs(v, u), dp[u]+=dp[v];
    res+=(dp[u])*(n-dp[u]);
    //cout<<"debug "<<u<<' '<<dp[u]<<' '<<res<<'\n';
}
int DistanceSum(int N, int *X, int *Y) {
    n=N;
    for (int i=0; i<N; i++) mpx[X[i]].push_back(Y[i]), mpy[Y[i]].push_back(X[i]);
    for (auto [x, y]:mpx) 
    {
        sort(y.begin(), y.end());
        ++t;
        if (mp.find({x-1, y[0]})!=mp.end()) d[mp[{x-1, y[0]}]].insert(t), d[t].insert(mp[{x-1, y[0]}]);
        mp[{x, y[0]}]=t;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i=1; i<y.size(); i++)
      |                       ~^~~~~~~~~
city.cpp:51:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i=1; i<y.size(); i++)
      |                       ~^~~~~~~~~

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