Submission #912883

#	Time	Username	Problem	Language	Result	Execution time	Memory
912883		Sir_Ahmed_Imran	Ideal city (IOI12_city)	C++17	Compilation error	0 ms	0 KiB

city

                              ///~~~LOTA~~~///
#include "city.h"
#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:2:10: fatal error: city.h: No such file or directory
    2 | #include "city.h"
      |          ^~~~~~~~
compilation terminated.