Submission #70900

#	Time	Username	Problem	Language	Result	Execution time	Memory
70900		MANcity	Ideal city (IOI12_city)	C++14	32 / 100	212 ms	16864 KiB

city

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
const LL maMod=1000*1000*1000;
int N;
int X[2002];
int Y[2002];
int dist[2002][2002];
int used[2002];
vector<vector<int> > g(2002);
void bfs(int v)
{
    int p_now=v;
    for0(i,N-1)
        used[i]=0;
    queue<int> myque;
    myque.push(v);
    while(!myque.empty())
    {
        int v=myque.front();
        for0(j,g[v].size()-1)
        {
            int to=g[v][j];
            if(used[to]==0)
            {
                dist[p_now][to]=dist[p_now][v]+1;
                used[to]=1;
                myque.push(to);
            }
        }
        myque.pop();
    }
}
int DistanceSum(int N_0, int *X_0, int *Y_0) {
    N=N_0;
    for0(i,N-1)
        X[i]=X_0[i];
    for0(i,N-1)
        Y[i]=Y_0[i];
    for0(i,N-1)
        for0(j,N-1)
        {
            if(i!=j)
            {
                int dist=abs(X[i]-X[j])+abs(Y[i]-Y[j]);
                if(dist==1)
                {
                    g[i].push_back(j);
                }
            }
        }
    for0(i,N-1)
        bfs(i);
    LL sumdist=0;
    for0(i,N-1)
        fo(j,i+1,N-1)
            sumdist=(sumdist+dist[i][j])%Mod;
    return sumdist;
}
/*11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
*/

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