oj.uz

Submission #481888

# Submission time Handle Problem Language Result Execution time Memory
481888 2021-10-22T06:01:35 Z Haruto810198 Ideal city (IOI12_city) C++17
32 / 100
 107 ms 3856 KB 
#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
//const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

const int MAX = 2010;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int n;
map<pii, int> mp;
vi edge[MAX];
int res;

int dis[MAX];
queue<int> qu;

int bfs(int st){
    FOR(i, 0, n-1, 1){
        dis[i] = INF;
    }
    dis[st] = 0;

    qu.push(st);
    while(!qu.empty()){
        int v = qu.front();
        qu.pop();
        for(int i : edge[v]){
            if(dis[i] == INF){
                dis[i] = dis[v] + 1;
                qu.push(i);
            }
        }
    }

    int ret = 0;
    FOR(i, 0, n-1, 1){
        ret += dis[i];
    }
    return ret;
}

int DistanceSum(int N, int *X, int *Y){
    n = N;

    FOR(i, 0, N-1, 1){
        mp[mkp(X[i], Y[i])] = i;
        cerr<<X[i]<<" "<<Y[i]<<endl;
    }

    FOR(i, 0, N-1, 1){
        FOR(j, 0, 3, 1){
            pii pt = mkp(X[i] + dx[j], Y[i] + dy[j]);
            if(mp.find(pt) != mp.end()) edge[i].pb(mp[pt]);
            //if(mp.find(pt) != mp.end()) cerr<<"edge "<<i<<", "<<j<<": "<<1<<endl;
            //else cerr<<"edge "<<i<<", "<<j<<": "<<0<<endl;
        }
    }

    FOR(i, 0, N-1, 1){
        res += bfs(i);
        //cerr<<"bfs("<<i<<") = "<<bfs(i)<<endl;
    }

    res /= 2;

    return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 352 KB Output is correct
2 Correct 28 ms 484 KB Output is correct
3 Correct 59 ms 464 KB Output is correct
4 Correct 61 ms 532 KB Output is correct
5 Correct 102 ms 488 KB Output is correct
6 Correct 95 ms 588 KB Output is correct
7 Correct 107 ms 472 KB Output is correct
8 Correct 104 ms 608 KB Output is correct
9 Correct 95 ms 460 KB Output is correct
10 Correct 93 ms 588 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 3784 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 102 ms 3856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -