oj.uz

Submission #163142

# Submission time Handle Problem Language Result Execution time Memory
163142 2019-11-11T13:51:55 Z mhy908 Ideal city (IOI12_city) C++14
100 / 100
 65 ms 15060 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=987654321987654321;
const int inf=987654321;
int a, tx, ty, tmp, t, x[100010], y[100010];
LL sum, mod=1e9, sz[100010];
vector<int> grid[100002], edge[100010];
struct data{
    int num, s, e;
};
vector<data> T[100010];

void dfs(int r, int par){
    for(int k=0; k<edge[r].size(); k++){
        if(par==edge[r][k])continue;
        dfs(edge[r][k], r);
        sz[r]+=sz[edge[r][k]];
    }
    sum+=sz[r]*(LL)(a-sz[r]);
}
void func()
{
    t=0;
    for(int i=0; i<=a; i++)grid[i].clear(), T[i].clear(), edge[i].clear();
    for(int i=1; i<=a; i++)grid[x[i]].push_back(y[i]);
    for(int i=0; grid[i].size(); i++)sort(grid[i].begin(), grid[i].end());
    for(int i=0; grid[i].size(); i++){
        tmp=grid[i][0];
        for(int j=0; j<grid[i].size(); j++){
            if(j==grid[i].size()-1||grid[i][j]+1!=grid[i][j+1]){
                T[i].push_back({t++, tmp, grid[i][j]});
                sz[t-1]=grid[i][j]-tmp+1;
                if(j!=grid[i].size()-1)tmp=grid[i][j+1];
            }
        }
    }
    for(int i=1; T[i].size(); i++){
        int p=0, q=0;
        while(p<T[i-1].size()&&q<T[i].size()){
            if(!(T[i-1][p].e<T[i][q].s||T[i][q].e<T[i-1][p].s)){
                edge[T[i-1][p].num].push_back(T[i][q].num);
                edge[T[i][q].num].push_back(T[i-1][p].num);
            }
            if(T[i-1][p].e<T[i][q].e)p++;
            else q++;
        }
    }
    dfs(0, -1);
}
int DistanceSum(int N, int *X, int *Y)
{
    a=N;
    tx=inf;
    ty=inf;
    for(int i=1; i<=a; i++)x[i]=X[i-1], y[i]=Y[i-1];
    for(int i=1; i<=a; i++)tx=min(tx,x[i]), ty=min(ty,y[i]);
    for(int i=1; i<=a; i++)x[i]-=tx, y[i]-=ty;
    func();
    for(int i=1; i<=a; i++)t=x[i], x[i]=y[i], y[i]=t;
    func();
    return sum%mod;
}

Compilation message

city.cpp: In function 'void dfs(int, int)':
city.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0; k<edge[r].size(); k++){
                  ~^~~~~~~~~~~~~~~
city.cpp: In function 'void func()':
city.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<grid[i].size(); j++){
                      ~^~~~~~~~~~~~~~~
city.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(j==grid[i].size()-1||grid[i][j]+1!=grid[i][j+1]){
                ~^~~~~~~~~~~~~~~~~~
city.cpp:41:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(j!=grid[i].size()-1)tmp=grid[i][j+1];
                    ~^~~~~~~~~~~~~~~~~~
city.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(p<T[i-1].size()&&q<T[i].size()){
               ~^~~~~~~~~~~~~~
city.cpp:47:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(p<T[i-1].size()&&q<T[i].size()){
                                ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 8 ms 7420 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 8 ms 7416 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 8 ms 7452 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 9 ms 7420 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7544 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 10 ms 7544 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 9 ms 7544 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8184 KB Output is correct
2 Correct 16 ms 8312 KB Output is correct
3 Correct 27 ms 8952 KB Output is correct
4 Correct 27 ms 9244 KB Output is correct
5 Correct 44 ms 10564 KB Output is correct
6 Correct 47 ms 11128 KB Output is correct
7 Correct 47 ms 11148 KB Output is correct
8 Correct 45 ms 10488 KB Output is correct
9 Correct 49 ms 11256 KB Output is correct
10 Correct 65 ms 15060 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8696 KB Output is correct
2 Correct 17 ms 8440 KB Output is correct
3 Correct 34 ms 10360 KB Output is correct
4 Correct 31 ms 9976 KB Output is correct
5 Correct 59 ms 13304 KB Output is correct
6 Correct 49 ms 11744 KB Output is correct
7 Correct 59 ms 13124 KB Output is correct
8 Correct 54 ms 11896 KB Output is correct
9 Correct 48 ms 11104 KB Output is correct
10 Correct 49 ms 11360 KB Output is correct