oj.uz

Submission #315829

# Submission time Handle Problem Language Result Execution time Memory
315829 2020-10-24T04:19:37 Z juggernaut Ideal city (IOI12_city) C++14
100 / 100
 56 ms 7924 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
#ifdef EVAL
#else
#include"grader.cpp"
#endif
using namespace std;
pair<int,int>p[100005];
vector<int>g[100005];
vector<pair<int,pair<int,int>>>cur;
int n,res;
typedef long long ll;
int dfs(int v,int p){
    int sz=cur[v].sc.sc-cur[v].sc.fr+1;
    for(auto to:g[v])
        if(to!=p)sz+=dfs(to,v);
    res=((ll)res+((ll)sz*(ll)(n-sz)))%1000000000ll;
    return sz;
}
void build_tree(){
    cur.clear();
    sort(p,p+n);
    for(int l=0;l<n;l++){
        int r=l;
        while(r+1<n&&p[r+1].fr==p[l].fr&&p[r+1].sc==p[r].sc+1)r++;
        cur.push_back({p[l].fr,{p[l].sc,p[r].sc}});
        l=r;
    }
    for(int i=0;i<cur.size();i++)g[i].resize(0);
    int r=0;
    for(int l=0;l<cur.size();l++){
        while(r<cur.size()&&cur[r].fr<cur[l].fr+1)r++;
        if(r==cur.size())break;
        while(r<n-1&&cur[r].sc.sc<cur[l].sc.fr&&cur[r].fr==cur[l].fr+1)r++;
        while(r<=n-1&&cur[r].sc.sc<=cur[l].sc.sc&&cur[r].fr==cur[l].fr+1){
            g[l].push_back(r);
            g[r].push_back(l);
            r++;
        }
        if(r!=n&&cur[r].sc.fr<=cur[l].sc.sc&&cur[r].fr==cur[l].fr+1){
            g[l].push_back(r);
            g[r].push_back(l);
        }
    }
    dfs(0,0);
}
int DistanceSum(int N,int *X,int *Y){
    n=N;
    for(int i=0;i<n;i++)p[i]={X[i],Y[i]};
    build_tree();
    for(int i=0;i<n;i++)swap(p[i].fr,p[i].sc);
    build_tree();
    return res;
}

Compilation message

city.cpp: In function 'void build_tree()':
city.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<cur.size();i++)g[i].resize(0);
      |                 ~^~~~~~~~~~~
city.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int l=0;l<cur.size();l++){
      |                 ~^~~~~~~~~~~
city.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         while(r<cur.size()&&cur[r].fr<cur[l].fr+1)r++;
      |               ~^~~~~~~~~~~
city.cpp:34:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         if(r==cur.size())break;
      |            ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2560 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2720 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2756 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2688 KB Output is correct
9 Correct 3 ms 2816 KB Output is correct
10 Correct 3 ms 2688 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3240 KB Output is correct
2 Correct 10 ms 3200 KB Output is correct
3 Correct 22 ms 3968 KB Output is correct
4 Correct 22 ms 3968 KB Output is correct
5 Correct 44 ms 5120 KB Output is correct
6 Correct 44 ms 5112 KB Output is correct
7 Correct 44 ms 5368 KB Output is correct
8 Correct 44 ms 4984 KB Output is correct
9 Correct 44 ms 5240 KB Output is correct
10 Correct 46 ms 7924 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3584 KB Output is correct
2 Correct 11 ms 3456 KB Output is correct
3 Correct 28 ms 4852 KB Output is correct
4 Correct 26 ms 4544 KB Output is correct
5 Correct 56 ms 6896 KB Output is correct
6 Correct 49 ms 5944 KB Output is correct
7 Correct 56 ms 7024 KB Output is correct
8 Correct 48 ms 5944 KB Output is correct
9 Correct 49 ms 5688 KB Output is correct
10 Correct 47 ms 5560 KB Output is correct