oj.uz

Submission #101097

# Submission time Handle Problem Language Result Execution time Memory
101097 2019-03-16T14:18:25 Z ansol4328 Ideal city (IOI12_city) C++11
100 / 100
 115 ms 14968 KB 
#include<vector>
#include<algorithm>

using namespace std;
typedef long long ll;

struct in
{
    ll x, y, Vn, Hn, vc, hc;
    in() {}
    in(ll a, ll b) : x(a), y(b) {}
};

bool cmp1(const in &a, const in &b)
{
    return a.x<b.x || (a.x==b.x && a.y<b.y);
}

bool cmp2(const in &a, const in &b)
{
    return a.y<b.y || (a.y==b.y && a.x<b.x);
}

ll n;
in m[100005];
ll Vcnt[100005], Hcnt[100005];
vector<ll> Vlst[100005], Hlst[100005];
ll res;
const ll MOD=1e9;

ll dfs(ll v, ll prev, vector<ll> *lst, ll *cnt)
{
    ll s=cnt[v];
    for(int i=0 ; i<lst[v].size() ; i++)
    {
        ll nxt=lst[v][i];
        if(nxt!=prev) s+=dfs(nxt,v,lst,cnt);
    }
    (res+=(n-s)*s)%=MOD;
    return s;
}

int DistanceSum(int N, int *X, int *Y)
{
	n=N;
    for(int i=1 ; i<=n ; i++) m[i].x=X[i-1], m[i].y=Y[i-1];
    //make vertical node
    sort(m+1,m+1+n,cmp1);
    ll ncnt=0;
    for(int i=1 ; i<=n ; i++)
    {
        if(m[i].x!=m[i-1].x || (m[i].x==m[i-1].x && m[i].y-m[i-1].y>1)) ncnt++;
        m[i].Vn=ncnt;
        Vcnt[ncnt]++;
        m[i].vc=Vcnt[ncnt];
    }
    //make horizontal node and vertical edge
    sort(m+1,m+1+n,cmp2);
    ncnt=0;
    for(int i=1 ; i<=n ; i++)
    {
        if(m[i].y!=m[i-1].y || (m[i].y==m[i-1].y && m[i].x-m[i-1].x>1)) ncnt++;
        m[i].Hn=ncnt;
        Hcnt[ncnt]++;
        m[i].hc=Hcnt[ncnt];
        if(m[i].y==m[i-1].y && m[i].x-m[i-1].x==1 && (m[i].vc==Vcnt[m[i].Vn] || m[i-1].vc==Vcnt[m[i-1].Vn]))
            Vlst[m[i].Vn].push_back(m[i-1].Vn), Vlst[m[i-1].Vn].push_back(m[i].Vn);
    }
    //make horizontal edge
    sort(m+1,m+1+n,cmp1);
    for(int i=1 ; i<=n ; i++)
    {
        if(m[i].x==m[i-1].x && m[i].y-m[i-1].y==1 && (m[i].hc==Hcnt[m[i].Hn] || m[i-1].hc==Hcnt[m[i-1].Hn]))
            Hlst[m[i].Hn].push_back(m[i-1].Hn), Hlst[m[i-1].Hn].push_back(m[i].Hn);
    }
    dfs(1,0,Vlst,Vcnt);
    dfs(1,0,Hlst,Hcnt);
    int ret=res;
    return ret;
}

Compilation message

city.cpp: In function 'll dfs(ll, ll, std::vector<long long int>*, ll*)':
city.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0 ; i<lst[v].size() ; i++)
                   ~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6392 KB Output is correct
2 Correct 20 ms 6400 KB Output is correct
3 Correct 39 ms 8312 KB Output is correct
4 Correct 42 ms 8184 KB Output is correct
5 Correct 88 ms 11384 KB Output is correct
6 Correct 72 ms 11512 KB Output is correct
7 Correct 88 ms 11640 KB Output is correct
8 Correct 94 ms 11400 KB Output is correct
9 Correct 91 ms 11640 KB Output is correct
10 Correct 82 ms 14968 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7012 KB Output is correct
2 Correct 21 ms 6784 KB Output is correct
3 Correct 55 ms 9976 KB Output is correct
4 Correct 46 ms 9308 KB Output is correct
5 Correct 105 ms 14844 KB Output is correct
6 Correct 79 ms 12792 KB Output is correct
7 Correct 115 ms 14968 KB Output is correct
8 Correct 103 ms 12920 KB Output is correct
9 Correct 113 ms 12280 KB Output is correct
10 Correct 111 ms 12280 KB Output is correct