oj.uz

Submission #1034385

# Submission time Handle Problem Language Result Execution time Memory
1034385 2024-07-25T13:02:16 Z idas Ideal city (IOI12_city) C++11
100 / 100
 114 ms 35536 KB 
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int MxN=1e5+10, mod=1e9;
ll cn[MxN][2], dp[MxN][2]; // how many nodes in group
map<pii, int> gr[2];
set<int> ad[MxN][2];

void build(int u, int k, int pst=-1)
{
//    cout << k << " -> " << u << '\n';
//    for(auto it : ad[u][k]){
//        cout << it << " ";
//    }
//    cout << '\n';

    dp[u][k]=cn[u][k];
    for(auto it : ad[u][k]){
        if(it==pst) continue;
        build(it, k, u);
        dp[u][k]+=dp[it][k];
    }
}

ll ans=0;
void dfs(int u, int k, ll up=0, int pst=-1)
{
    ans+=up*dp[u][k]%mod;
    ans%=mod;

    for(auto it : ad[u][k]){
        if(it==pst) continue;
        dfs(it, k, up+dp[u][k]-dp[it][k], u);
    }
}

int DistanceSum(int n, int x[], int y[]) {
    vector<pii> inf;
    FOR(i, 0, n)
    {
        inf.pb({x[i],y[i]});
    }
    sort(inf.begin(), inf.end());

    int now;
    FOR(k, 0, 2)
    {
//        cout << k << ":\n";
//        FOR(i, 0, n)
//        {
//            cout << inf[i].f << " " << inf[i].s << '\n';
//        }

        FOR(i, 0, n)
        {
            if(i==0 || inf[i-1].f!=inf[i].f || inf[i-1].s+1!=inf[i].s) now=i;

            int a=inf[i].f, b=inf[i].s;
            gr[k][{a,b}]=now;
            cn[now][k]++;

            if(gr[k].count({a-1,b})){
                int nxt=gr[k][{a-1,b}];
                ad[now][k].insert(nxt);
                ad[nxt][k].insert(now);
            }
        }

        build(0, k);
        dfs(0, k);

        FOR(i, 0, n) swap(inf[i].f, inf[i].s);
        sort(inf.begin(), inf.end());
    }

    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9816 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 10072 KB Output is correct
10 Correct 4 ms 9896 KB Output is correct
11 Correct 5 ms 9848 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10072 KB Output is correct
2 Correct 5 ms 10076 KB Output is correct
3 Correct 7 ms 10116 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 5 ms 10332 KB Output is correct
6 Correct 5 ms 10076 KB Output is correct
7 Correct 6 ms 10332 KB Output is correct
8 Correct 5 ms 10076 KB Output is correct
9 Correct 5 ms 10076 KB Output is correct
10 Correct 6 ms 10076 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13528 KB Output is correct
2 Correct 18 ms 13528 KB Output is correct
3 Correct 42 ms 18896 KB Output is correct
4 Correct 41 ms 18896 KB Output is correct
5 Correct 88 ms 27860 KB Output is correct
6 Correct 81 ms 28108 KB Output is correct
7 Correct 83 ms 28316 KB Output is correct
8 Correct 81 ms 27596 KB Output is correct
9 Correct 79 ms 28204 KB Output is correct
10 Correct 93 ms 33744 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15064 KB Output is correct
2 Correct 23 ms 14284 KB Output is correct
3 Correct 50 ms 22484 KB Output is correct
4 Correct 50 ms 21200 KB Output is correct
5 Correct 111 ms 35272 KB Output is correct
6 Correct 95 ms 30824 KB Output is correct
7 Correct 114 ms 35536 KB Output is correct
8 Correct 95 ms 31112 KB Output is correct
9 Correct 96 ms 30156 KB Output is correct
10 Correct 112 ms 29840 KB Output is correct