Submission #912885

#	Time	Username	Problem	Language	Result	Execution time	Memory
912885		Sir_Ahmed_Imran	Ideal city (IOI12_city)	C++17	0 / 100	53 ms	12788 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 tcnt[MAXN];
ll dist[MAXN];
int vis[MAXN];
ll tdist[MAXN];
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;
    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++){
            p=(cnt[vec[j]]*(dist[vec[i]]+cnt[vec[i]]))%mod;
            q=(cnt[vec[i]]*(dist[vec[j]]+cnt[vec[j]]))%mod;
            ans[v]=(ans[v]+p+q)%mod;
        }
    }
    if(par[v].size()>1){
        o=lca(v);
        p=par[v][0];
        q=par[v][1];
        tcnt[p]+=cnt[v];
        tcnt[q]+=cnt[v];
        tdist[p]+=dist[v]+cnt[v];
        tdist[q]+=dist[v]+cnt[v];
        cnt[o]+=cnt[v];
        dist[o]=(dist[o]+dist[v]+2*cnt[v])%mod;
    }
    cnt[v]-=tcnt[v];
    dist[v]-=tdist[v];
}
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;
    int m,o,p,q,r;
    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();
    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++){
      |                       ~^~~~~~~~~~~
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:97:9: warning: unused variable 'm' [-Wunused-variable]
   97 |     int m,o,p,q,r;
      |         ^
city.cpp:97:13: warning: unused variable 'p' [-Wunused-variable]
   97 |     int m,o,p,q,r;
      |             ^
city.cpp:97:15: warning: unused variable 'q' [-Wunused-variable]
   97 |     int m,o,p,q,r;
      |               ^
city.cpp:97:17: warning: unused variable 'r' [-Wunused-variable]
   97 |     int m,o,p,q,r;
      |                 ^

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