oj.uz

Submission #70900

# Submission time Handle Problem Language Result Execution time Memory
70900 2018-08-23T16:13:58 Z MANcity Ideal city (IOI12_city) C++14
32 / 100
 212 ms 16864 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 728 KB Output is correct
4 Correct 3 ms 1172 KB Output is correct
5 Correct 4 ms 1220 KB Output is correct
6 Correct 7 ms 1684 KB Output is correct
7 Correct 5 ms 1716 KB Output is correct
8 Correct 5 ms 1716 KB Output is correct
9 Correct 6 ms 1716 KB Output is correct
10 Correct 6 ms 1716 KB Output is correct
11 Correct 5 ms 1812 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 8728 KB Output is correct
2 Correct 48 ms 8736 KB Output is correct
3 Correct 149 ms 12536 KB Output is correct
4 Correct 113 ms 12676 KB Output is correct
5 Correct 178 ms 16672 KB Output is correct
6 Correct 206 ms 16720 KB Output is correct
7 Correct 212 ms 16720 KB Output is correct
8 Correct 187 ms 16720 KB Output is correct
9 Correct 187 ms 16736 KB Output is correct
10 Correct 203 ms 16864 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 16864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 16864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -