oj.uz

Submission #1701

# Submission time Handle Problem Language Result Execution time Memory
1701 2013-07-12T15:02:38 Z tncks0121 Ideal city (IOI12_city) C++
100 / 100
 68 ms 8024 KB 
#include<algorithm>
#include<vector>
 
using namespace std;
typedef long long lld;
 
const lld MOD = 1000000000;
 
struct P{
    int x, y;
    P(){} P(int x,int y): x(x), y(y) {}
    bool operator< (const P &t) const{
        if(x != t.x) return x < t.x;
        return y < t.y;
    }
} *Points;
 
struct Row{
    int x, uy, dy; vector<int> adj;
    Row() { x = uy = dy = 0; }
    Row(int x, int uy, int dy): x(x), uy(uy), dy(dy) {}
    int length(){ return dy - uy + 1; }
};
 
vector <Row> Rows;
 
void MakeGraph(int N){
    int i, j;
    std::sort(Points, Points + N);
    Rows.clear();
 
    // 정점 만들기
    for(i = 0; i < N; i = j){
        int x = Points[i].x, uy = Points[i].y, dy = Points[i].y;
        for(j = i + 1; j < N; ++j){
            if(Points[j].y == dy + 1) ++dy;
            else break;
        }
        Rows.push_back(Row(x, uy, dy));
    }
 
    // 간선 만들기
    int sz = Rows.size();
    for(i = 0, j = 1; j < sz; ++j){
        bool ck = 0;
        while(i < j && Rows[i].x + 1 < Rows[j].x || (Rows[i].x + 1 == Rows[j].x && Rows[i].dy < Rows[j].uy)) ++i;
        while(i < j && Rows[i].x + 1 == Rows[j].x && Rows[i].uy <= Rows[j].dy){
            ck = 1; Rows[i].adj.push_back(j); Rows[j].adj.push_back(i); ++i;
        } if(ck) --i;
    }
}
 
int *Que, Qf, Qr;
bool *Visited;
int *Parent;
int *SumSubTree;
 
int GetSum(int N){
    int i, j; lld ret = 0;
 
    MakeGraph(N);
    Que = (int*) calloc(N+1, sizeof(int));
    Parent = (int*) calloc(N+1, sizeof(int));
    Visited = (bool*) calloc(N+1, sizeof(bool));
 
    Qf = Qr = 0; Que[++Qr] = 0; Visited[0] = 1;
    while(Qf < Qr){
        int f = Que[++Qf]; int adjsz = Rows[f].adj.size();
        for(i = 0; i < adjsz; ++i){
            int g = Rows[f].adj[i]; if(!Visited[g]){
                Que[++Qr] = g; Visited[g] = 1;
                Parent[g] = f;
            }
        }
    }
 
    SumSubTree = (int*) calloc(N+1, sizeof(int));
    for(i = Qr; i > 1; --i){
        int v = Que[i]; int p = Parent[v];
        int thislen = Rows[v].length();
        SumSubTree[v] += thislen; SumSubTree[v] %= MOD;
        ret += ((lld)(N - SumSubTree[v]) * SumSubTree[v]) % MOD; ret %= MOD;
        SumSubTree[p] += SumSubTree[v]; SumSubTree[p] %= MOD;
    }
 
    free(Que); free(Visited); free(Parent);
    free(SumSubTree);
    return ret;
}
 
int DistanceSum(int N, int *X, int *Y){
    int i, j; lld ret1 = 0, ret2 = 0;
 
    Points = (P*) malloc(N * sizeof(P));
    for(i = 0; i < N; i++) Points[i] = P(X[i], Y[i]);
    ret1 = GetSum(N);
    for(i = 0; i < N; i++) Points[i] = P(Y[i], X[i]);
    ret2 = GetSum(N);
 
    free(Points);
    return (ret1 + ret2) % MOD;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1976 KB Output is correct
2 Correct 8 ms 1916 KB Output is correct
3 Correct 24 ms 2824 KB Output is correct
4 Correct 16 ms 2944 KB Output is correct
5 Correct 48 ms 4284 KB Output is correct
6 Correct 40 ms 4360 KB Output is correct
7 Correct 40 ms 4360 KB Output is correct
8 Correct 44 ms 4244 KB Output is correct
9 Correct 36 ms 4472 KB Output is correct
10 Correct 52 ms 6468 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2508 KB Output is correct
2 Correct 8 ms 2308 KB Output is correct
3 Correct 32 ms 4688 KB Output is correct
4 Correct 28 ms 3800 KB Output is correct
5 Correct 68 ms 8004 KB Output is correct
6 Correct 52 ms 5316 KB Output is correct
7 Correct 60 ms 8024 KB Output is correct
8 Correct 56 ms 5364 KB Output is correct
9 Correct 52 ms 5240 KB Output is correct
10 Correct 52 ms 5192 KB Output is correct