Submission #912988

#	Time	Username	Problem	Language	Result	Execution time	Memory
912988		Sir_Ahmed_Imran	Ideal city (IOI12_city)	C++17	0 / 100	77 ms	13836 KiB

city

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define mod 1000000000
#define MAXN 100001
ll ans[MAXN];
ll cnt[MAXN];
ll dist[MAXN];
int vis[MAXN];
map<pii,ll> ccnt;
map<pii,ll> cdist;
vector<int> a[MAXN];
vector<int> par[MAXN];
int lca(int x){
    int v,u,p,q,r,s;
    v=par[x][0];
    u=par[x][1];
    p=par[v][0];
    q=par[v].back();
    r=par[u][0];
    s=par[u].back();
    if(p==r || p==s) 
        return p;
    if(q==r || q==s) 
        return q;
    return 0;
}
void compute(int v){
    ll o,p,q,r,s;
    cnt[v]+=1;
    vector<int> vec;
    for(auto& i:a[v]){
        if(i!=par[v][0] &&
        i!=par[v].back())
            vec.append(i);
    }
    for(auto& i:vec){
        cnt[v]+=cnt[i];
        dist[v]=(dist[v]+dist[i]+cnt[i])%mod;
    }
    ans[v]+=dist[v];
    for(int i=0;i<vec.size();i++){
        for(int j=i+1;j<vec.size();j++){
            r=vec[i];
            s=vec[j];
            p=((cnt[r]-ccnt[{r,s}])*(dist[s]+cnt[s]-cdist[{r,s}]-ccnt[{r,s}]))%mod;
            q=((cnt[s]-ccnt[{r,s}])*(dist[r]+cnt[r]-cdist[{r,s}]-ccnt[{r,s}]))%mod;
            ans[v]=(ans[v]+p+q)%mod;
        }
    }
    //cout<<v<<' '<<cnt[v]<<' '<<dist[v]<<' '<<ans[v]<<nl;
    if(par[v].size()>1){
        o=lca(v);
        p=par[v][0];
        q=par[v][1];
        ccnt[{p,q}]=cnt[v];
        ccnt[{q,p}]=cnt[v];
        cdist[{p,q}]=dist[v]+cnt[v];
        cdist[{p,q}]=dist[v]+cnt[v];
        cnt[o]-=cnt[v];
        dist[o]-=dist[v]+2*cnt[v];
        dist[o]=((dist[o]%mod)+mod)%mod;
    }
}
void bfs(){
    vis[1]=1;
    par[1].append(0);
    vector<int> u,v{1};
    vector<vector<int>> vec;
    while(!v.empty()){
        vec.append(v);
        for(auto& j:v){
            for(auto& i:a[j]){
                if(i!=par[j][0] &&
                i!=par[j].back())
                    par[i].append(j);
                if(!vis[i])
                    u.append(i);
                vis[i]=1;
            }
        }
        swap(v,u);
        u.clear();
    }
    reverse(all(vec));
    for(auto& i:vec)
        for(auto& j:i)
            compute(j);
}
int DistanceSum(int n,int x[MAXN],int y[MAXN]){
    map<pii,int> z;
    for(int i=0;i<n;i++){
        z[{x[i],y[i]}]=i+1;
        if(z[{x[i],y[i]-1}]){
            a[z[{x[i],y[i]-1}]].append(i+1);
            a[i+1].append(z[{x[i],y[i]-1}]);
        }
        if(z[{x[i],y[i]+1}]){
            a[z[{x[i],y[i]+1}]].append(i+1);
            a[i+1].append(z[{x[i],y[i]+1}]);
        }
        if(z[{x[i]-1,y[i]}]){
            a[z[{x[i]-1,y[i]}]].append(i+1);
            a[i+1].append(z[{x[i]-1,y[i]}]);
        }
        if(z[{x[i]+1,y[i]}]){
            a[z[{x[i]+1,y[i]}]].append(i+1);
            a[i+1].append(z[{x[i]+1,y[i]}]);
        }
    }
    bfs();
    ll o=0;
    for(int i=1;i<=n;i++)
        o=(o+ans[i])%mod;
    return o;
}

Compilation message (stderr)

city.cpp: In function 'void compute(int)':
city.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<vec.size();i++){
      |                 ~^~~~~~~~~~~
city.cpp:50:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int j=i+1;j<vec.size();j++){
      |                       ~^~~~~~~~~~~

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