oj.uz

Submission #868884

# Submission time Handle Problem Language Result Execution time Memory
868884 2023-11-02T11:25:36 Z HuyQuang_re_Zero Ideal city (IOI12_city) C++14
100 / 100
 109 ms 18056 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define N 100005
using namespace std;
struct pt { int x,y,pos; } a[N];
struct International_Olympiad_in_Informatics
{
    vector <int> a[N];
    ll n,i,j,step,u,v,mod=1e9,sz[N],res,node[N];
    void DFS(int u,int p)
    {
        for(int v:a[u])
            if(v!=p)
            {
                DFS(v,u);
                sz[u]+=sz[v];
                res=(res+sz[v]*(n-sz[v]))%mod;
            }
    }
    int Work(int _n,pt cell[])
    {
        n=_n;
        res=0;
        for(step=0;step<=1;step++)
        {
            map <II,int> num;
            memset(sz,0,sizeof(sz));
            sort(cell+1,cell+n+1,[&](pt a,pt b){ return (a.x<b.x || (a.x==b.x && a.y<b.y)); });
            for(i=1;i<=n;i++)
            {
                num[make_pair(cell[i].x,cell[i].y)]=i;
                a[i].clear();
            }
            int u=1;
            for(i=1;i<=n;i++)
            {
                node[i]=u;
                if(i==n || cell[i+1].x>cell[i].x || (cell[i+1].x==cell[i].x && cell[i].y+1<cell[i+1].y))
                {
                    set <int> s;
                    for(j=i;node[j]==u;j--)
                    {
                        s.insert(node[num[make_pair(cell[j].x-1,cell[j].y)]]);
                        sz[u]++;
                    }
                    for(int v:s)
                        if(v>0)
                        {
                            a[u].push_back(v),a[v].push_back(u);
                        }
                    u++;
                }
            }
            DFS(1,0);

            for(i=1;i<=n;i++) swap(cell[i].x,cell[i].y);
        }
        return res;
    }
} IOI;

int x[N],y[N],n,i;

int DistanceSum(int n,int _x[], int _y[])
{
    for(int i=n;i>=1;i--) a[i].x=_x[i-1],a[i].y=_y[i-1];
    return IOI.Work(n,a);
}
/*
int main()
{
    freopen("city.inp","r",stdin);
    freopen("city.out","w",stdout);
    cin>>n;
    for(i=0;i<n;i++) cin>>x[i]>>y[i];
    cout<<DistanceSum(n,x,y);
}
*/

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6744 KB Output is correct
2 Correct 14 ms 6236 KB Output is correct
3 Correct 37 ms 9052 KB Output is correct
4 Correct 36 ms 9048 KB Output is correct
5 Correct 70 ms 14092 KB Output is correct
6 Correct 78 ms 13944 KB Output is correct
7 Correct 69 ms 14324 KB Output is correct
8 Correct 80 ms 13832 KB Output is correct
9 Correct 79 ms 14208 KB Output is correct
10 Correct 99 ms 18056 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7000 KB Output is correct
2 Correct 15 ms 6748 KB Output is correct
3 Correct 45 ms 10840 KB Output is correct
4 Correct 40 ms 10320 KB Output is correct
5 Correct 109 ms 17800 KB Output is correct
6 Correct 82 ms 15536 KB Output is correct
7 Correct 94 ms 17732 KB Output is correct
8 Correct 91 ms 15640 KB Output is correct
9 Correct 93 ms 15184 KB Output is correct
10 Correct 81 ms 15056 KB Output is correct