Submission #315829

#	Time	Username	Problem	Language	Result	Execution time	Memory
315829		juggernaut	Ideal city (IOI12_city)	C++14	100 / 100	56 ms	7924 KiB

city

#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 (stderr)

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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45