oj.uz

Submission #587281

# Submission time Handle Problem Language Result Execution time Memory
587281 2022-07-01T15:04:07 Z mosiashvililuka Ideal city (IOI12_city) C++14
100 / 100
 179 ms 23908 KB 
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,cnt,lf[100009],rg[100009],id[100009],X[100009],Y[100009],J,I,mod=1000000000LL,pas,dp[100009];
vector <pair <long long, long long> > v[100009];
map <long long, vector <pair <long long, long long> > > m;
map <long long, vector <pair <long long, long long> > >::iterator it;
map <pair <long long, long long>, long long> n,EDGE;
map <pair <long long, long long>, long long>::iterator tt;
vector <pair <long long, long long> > vv;
long long jami(long long q){
    long long qw=q*(q+1)/2LL;qw%=mod;
    return qw;
}
void dfsst(int q, int w){
    dp[q]=rg[q]-lf[q]+1;
    for(vector <pair <long long, long long> >::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it).first==w) continue;
        dfsst((*it).first,q);
        dp[q]+=dp[(*it).first];
    }
}
void dfs(int q, int w){
    for(vector <pair <long long, long long> >::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it).first==w) continue;
        dfs((*it).first,q);
        zx=dp[(*it).first]*(a-dp[(*it).first]);zx%=mod;
        pas+=zx;pas%=mod;
    }
}
long long fun(long long l, long long r, long long L, long long R){
    long long jm=0;
    /*for(long long h=L; h<=R; h++){
        if(l<=h&&h<=r){
            jm+=jami(h-l)+jami(r-h)+r-l+1;jm%=mod;
            continue;
        }
        if(r<h){
            jm+=jami(h-l-(h-r))+(r-l+1)*(h-r+1);jm%=mod;
            continue;
        }
        if(l>h){
            jm+=jami(r-h-(l-h))/+(r-l+1)*(l-h+1);jm%=mod;
            continue;
        }
    }*/
    jm=(r-l+1)*(R-L+1);jm%=mod;
    return jm;
}
int DistanceSum(int NN, int *XX, int *YY) {
    a=NN;
    for(i=1; i<=a; i++){
        c=XX[i-1];d=YY[i-1];
        X[i]=c;Y[i]=d;
        m[c].push_back({d,i});
    }
    for(it=m.begin(); it!=m.end(); it++){
        sort((*it).second.begin(),(*it).second.end());
    }
    for(it=m.begin(); it!=m.end(); it++){
        vv=(*it).second;
        cnt++;
        id[vv[0].second]=cnt;
        lf[cnt]=rg[cnt]=vv[0].first;
        i=(*it).first;j=vv[0].first;
        n[{i,j}]=cnt;
        for(jj=1; jj<vv.size(); jj++){
            if(vv[jj-1].first+1==vv[jj].first){
                rg[cnt]=vv[jj].first;
            }else{
                cnt++;
                lf[cnt]=rg[cnt]=vv[jj].first;
            }
            id[vv[jj].second]=cnt;
            i=(*it).first;j=vv[jj].first;
            n[{i,j}]=cnt;
        }
    }
    for(it=m.begin(); it!=m.end(); it++){
        vv=(*it).second;
        for(J=0; J<vv.size(); J++){
            i=(*it).first;j=vv[J].first;
            c=n[{i,j}];
            ii=i-1;jj=j;
            d=n[{ii,jj}];
            if(d==0) continue;
            //cout<<c<<" EDGE "<<d<<"\n";
            /*for(I=lf[c]; I<=rg[c]; I++){
                zx=jami(I-lf[d])+jami(rg[d]-I)+rg[d]-lf[d]+1;zx%=mod;
                EDGE[{c,d}]+=zx;EDGE[{c,d}]%=mod;
            }*/
            if(EDGE[{c,d}]==1) continue;
            EDGE[{c,d}]=1;
            e=fun(lf[c],rg[c],lf[d],rg[d]);
            v[c].push_back({d,e});
            v[d].push_back({c,e});
            //cout<<c<<" "<<d<<"   "<<e<<"    FR   "<<lf[c]<<" "<<rg[c]<<"  "<<lf[d]<<" "<<rg[d]<<"\n";
        }
    }
    /*for(tt=EDGE.begin(); tt!=EDGE.end(); tt++){
        v[(*tt).first.first].push_back({(*tt).first.second,(*tt).second});
        v[(*tt).first.second].push_back({(*tt).first.first,(*tt).second});
        cout<<(*tt).first.first<<" "<<(*tt).first.second<<"   "<<(*tt).second<<"\n";
    }*/

    dfsst(1,0);
    dfs(1,0);




    //
    m.clear();cnt=0;n.clear();EDGE.clear();
    for(i=0; i<=a+1; i++){
        v[i].clear();
    }



    for(i=1; i<=a; i++){
        c=XX[i-1];d=YY[i-1];
        swap(c,d);
        X[i]=c;Y[i]=d;
        m[c].push_back({d,i});
    }
    for(it=m.begin(); it!=m.end(); it++){
        sort((*it).second.begin(),(*it).second.end());
    }
    for(it=m.begin(); it!=m.end(); it++){
        vv=(*it).second;
        cnt++;
        id[vv[0].second]=cnt;
        lf[cnt]=rg[cnt]=vv[0].first;
        i=(*it).first;j=vv[0].first;
        n[{i,j}]=cnt;
        for(jj=1; jj<vv.size(); jj++){
            if(vv[jj-1].first+1==vv[jj].first){
                rg[cnt]=vv[jj].first;
            }else{
                cnt++;
                lf[cnt]=rg[cnt]=vv[jj].first;
            }
            id[vv[jj].second]=cnt;
            i=(*it).first;j=vv[jj].first;
            n[{i,j}]=cnt;
        }
    }
    for(it=m.begin(); it!=m.end(); it++){
        vv=(*it).second;
        for(J=0; J<vv.size(); J++){
            i=(*it).first;j=vv[J].first;
            c=n[{i,j}];
            ii=i-1;jj=j;
            d=n[{ii,jj}];
            if(d==0) continue;
            //cout<<c<<" EDGE "<<d<<"\n";
            /*for(I=lf[c]; I<=rg[c]; I++){
                zx=jami(I-lf[d])+jami(rg[d]-I)+rg[d]-lf[d]+1;zx%=mod;
                EDGE[{c,d}]+=zx;EDGE[{c,d}]%=mod;
            }*/
            if(EDGE[{c,d}]==1) continue;
            EDGE[{c,d}]=1;
            e=fun(lf[c],rg[c],lf[d],rg[d]);
            v[c].push_back({d,e});
            v[d].push_back({c,e});
            //cout<<c<<" "<<d<<"   "<<e<<"    SC   "<<lf[c]<<" "<<rg[c]<<"  "<<lf[d]<<" "<<rg[d]<<"\n";
        }
    }
    /*for(tt=EDGE.begin(); tt!=EDGE.end(); tt++){
        v[(*tt).first.first].push_back({(*tt).first.second,(*tt).second});
        v[(*tt).first.second].push_back({(*tt).first.first,(*tt).second});
        cout<<(*tt).first.first<<" "<<(*tt).first.second<<"   "<<(*tt).second<<"\n";
    }*/

    dfsst(1,0);
    dfs(1,0);



















    //

    int PAS=pas;
    return PAS;
}

Compilation message

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:66:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(jj=1; jj<vv.size(); jj++){
      |                   ~~^~~~~~~~~~
city.cpp:80:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(J=0; J<vv.size(); J++){
      |                  ~^~~~~~~~~~
city.cpp:135:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for(jj=1; jj<vv.size(); jj++){
      |                   ~~^~~~~~~~~~
city.cpp:149:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for(J=0; J<vv.size(); J++){
      |                  ~^~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2800 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 3 ms 2928 KB Output is correct
4 Correct 3 ms 2900 KB Output is correct
5 Correct 4 ms 3056 KB Output is correct
6 Correct 4 ms 3028 KB Output is correct
7 Correct 4 ms 3056 KB Output is correct
8 Correct 5 ms 3028 KB Output is correct
9 Correct 4 ms 2900 KB Output is correct
10 Correct 3 ms 2932 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5296 KB Output is correct
2 Correct 22 ms 5376 KB Output is correct
3 Correct 64 ms 9076 KB Output is correct
4 Correct 57 ms 9036 KB Output is correct
5 Correct 128 ms 15596 KB Output is correct
6 Correct 116 ms 15772 KB Output is correct
7 Correct 123 ms 15916 KB Output is correct
8 Correct 130 ms 15484 KB Output is correct
9 Correct 133 ms 15440 KB Output is correct
10 Correct 160 ms 23812 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6988 KB Output is correct
2 Correct 31 ms 6356 KB Output is correct
3 Correct 76 ms 13164 KB Output is correct
4 Correct 69 ms 11616 KB Output is correct
5 Correct 179 ms 23724 KB Output is correct
6 Correct 133 ms 18560 KB Output is correct
7 Correct 173 ms 23908 KB Output is correct
8 Correct 140 ms 18872 KB Output is correct
9 Correct 129 ms 17724 KB Output is correct
10 Correct 133 ms 17484 KB Output is correct