# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
912861 | Faisal_Saqib | Ideal city (IOI12_city) | C++17 | 1020 ms | 856 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma once
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
/*
1 11 N <= 2e2 O(n^2)
2 21 N <= 2e3 O(n^2)
3 23 N <= 1e5
4 45 N <= 1e5
For 3 any two cell such x[i]<=x[j] then for all x such that x[i]<=x<=x[j] there is non empty cell there
*/
const int N=2001;
vector<int> ma[N];
bool vis[N];
int h[N];
int DistanceSum(int n, int x[], int y[])
{
if(n<=2000)
{
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if((abs(x[i]-x[j])+abs(y[i]-y[j]))==1)
{
ma[i].push_back(j);
ma[j].push_back(i);
}
}
}
long long ans1=0;
long long mod=1e9;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
h[j]=0;
vis[j]=0;
}
queue<int> q;
q.push(i);
vis[i]=1;
long long ans=0;
while(q.size())
{
int x=q.front();
ans+=(long long)h[x];
q.pop();
for(int y:ma[x])
{
if(!vis[y])
{
vis[y]=1;
h[y]=h[x]+1;
q.push(y);
}
}
}
ans1+=ans;
}
ans1/=2;
return ans1%mod;
}
long long other=0;
long long mod=1e9;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
other+=(abs(x[i]-x[j])+abs(y[i]-y[j]));
other%=mod;
}
}
return other%mod;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |