Submission #1701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1701		tncks0121	Ideal city (IOI12_city)	C++98	100 / 100	68 ms	8024 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45