oj.uz

Submission #426458

# Submission time Handle Problem Language Result Execution time Memory
426458 2021-06-14T04:16:16 Z Amylopectin City Mapping (NOI18_citymapping) C++14
95.47 / 100
 8 ms 7628 KB 
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include "citymapping.h"
//#include "grader.cpp"
using namespace std;
const int mxn = 1010;
struct we
{
    long long no,dis;
};
struct pat
{
    long long fr,to,dis;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.dis < r.dis;
}
struct pat apa[mxn] = {};
long long di[mxn][mxn] = {},li[mxn][mxn] = {},cli[mxn] = {},u[mxn] = {},ncli[mxn] = {},capa = 0;
//struct we fli[mxn] = {};
long long re(long long cn,long long la)
{
    if(cli[cn] == 0)
    {
        return 0;
    }
    if(cli[cn] == 1)
    {
        apa[capa] = {cn,li[cn][0],di[cn][li[cn][0]]};
        capa ++;
        return 0;
    }
    long long i,fn,cma = -1,mno = -1,cou = 0,cva,cl,cr,mid,tn,nco = 0;
    struct we fli[mxn] = {};
//    for(i=0; i<cli[cn]; i++)
//    {
//        fn = li[cn][i];
//        if(di[cn][fn] > cma)
//        {
//            cma = di[cn][fn];
//            mno = fn;
//        }
//    }
    mno = rand() % cli[cn];
    mno = li[cn][mno];
    u[mno] = la;
    for(i=0; i<cli[cn]; i++)
    {
        fn = li[cn][i];
        if(fn == mno)
        {
            continue;
        }
        di[mno][fn] = get_distance(mno,fn);
        if(di[mno][fn] + di[cn][fn] == di[cn][mno])
        {
            fli[cou] = {fn,di[cn][fn]};
            cou ++;
            u[fn] = la;
        }
    }
    fli[cou] = {cn,0};
    cou ++;
    sort(fli,fli+cou,cmp);
    fli[cou] = {mno,di[cn][mno]};
    cou ++;
    for(i=0; i<cli[cn]; i++)
    {
        fn = li[cn][i];
        if(u[fn] == la)
        {
            continue;
        }
        cva = di[cn][fn] - (di[cn][fn] + di[mno][fn] - di[cn][mno]) / 2;
        cl = 0;
        cr = cou - 1;
        while(cl < cr)
        {
            mid = (cl+cr) / 2;
            if(fli[mid].dis >= cva)
            {
                cr = mid;
            }
            else
            {
                cl = mid+1;
            }
        }
        tn = fli[cl].no;
        di[tn][fn] = di[cn][fn] - di[cn][tn];
        if(tn == cn)
        {
            li[tn][nco] = fn;
            nco ++;
        }
        else
        {
            li[tn][cli[tn]] = fn;
            cli[tn] ++;
        }
    }
    cli[cn] = nco;
    for(i=0; i<cou-1; i++)
    {
        fn = fli[i].no;
        tn = fli[i+1].no;
        apa[capa] = {fn,tn,di[cn][tn] - di[cn][fn]};
        capa ++;
        re(fn,la+1);
    }
    re(tn,la+1);
    return 0;
}
void find_roads(int n, int q, int a[], int b[], int w[])
{
    int i,j,stn = (rand() % n) + 1;
//    stn = 8;
    for(i=1; i<=n; i++)
    {
        if(i != stn)
        {
            di[stn][i] = get_distance(stn,i);
            li[stn][cli[stn]] = i;
            cli[stn] ++;
        }
    }
    re(stn,1);
    for(i=0; i<n-1; i++)
    {
        a[i] = apa[i].fr;
        b[i] = apa[i].to;
        w[i] = apa[i].dis;
    }
//	for (int i = 0; i < N - 1; i++)
//	{
//		A[i] = 1;
//		B[i] = 2;
//		W[i] = 1;
//	}
	return;
}
//int main()
//{
//    int i,j,n,m;
//    scanf("%d")
//    return 0;
//}

Compilation message

citymapping.cpp: In function 'long long int re(long long int, long long int)':
citymapping.cpp:36:20: warning: unused variable 'cma' [-Wunused-variable]
   36 |     long long i,fn,cma = -1,mno = -1,cou = 0,cva,cl,cr,mid,tn,nco = 0;
      |                    ^~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:119:11: warning: unused variable 'j' [-Wunused-variable]
  119 |     int i,j,stn = (rand() % n) + 1;
      |           ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Correct: 2781 out of 500000 queries used.
2 Correct 4 ms 4684 KB Correct: 2896 out of 500000 queries used.
3 Correct 5 ms 6732 KB Correct: 5065 out of 500000 queries used.
4 Correct 5 ms 7500 KB Correct: 5831 out of 500000 queries used.
5 Correct 4 ms 2252 KB Correct: 4765 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Correct: 2781 out of 500000 queries used.
2 Correct 4 ms 4684 KB Correct: 2896 out of 500000 queries used.
3 Correct 5 ms 6732 KB Correct: 5065 out of 500000 queries used.
4 Correct 5 ms 7500 KB Correct: 5831 out of 500000 queries used.
5 Correct 4 ms 2252 KB Correct: 4765 out of 500000 queries used.
6 Correct 2 ms 972 KB Correct: 4054 out of 500000 queries used.
7 Correct 4 ms 4672 KB Correct: 3759 out of 500000 queries used.
8 Correct 7 ms 6732 KB Correct: 4800 out of 500000 queries used.
9 Correct 7 ms 7500 KB Correct: 5240 out of 500000 queries used.
10 Correct 4 ms 2380 KB Correct: 4174 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Correct: 2604 out of 12000 queries used.
2 Correct 2 ms 844 KB Correct: 2743 out of 12000 queries used.
3 Correct 2 ms 716 KB Correct: 2626 out of 12000 queries used.
4 Correct 2 ms 972 KB Correct: 4226 out of 12000 queries used.
5 Correct 3 ms 844 KB Correct: 3715 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Correct: 2604 out of 12000 queries used.
2 Correct 2 ms 844 KB Correct: 2743 out of 12000 queries used.
3 Correct 2 ms 716 KB Correct: 2626 out of 12000 queries used.
4 Correct 2 ms 972 KB Correct: 4226 out of 12000 queries used.
5 Correct 3 ms 844 KB Correct: 3715 out of 12000 queries used.
6 Correct 3 ms 1072 KB Correct: 3996 out of 12000 queries used.
7 Correct 2 ms 844 KB Correct: 3646 out of 12000 queries used.
8 Correct 2 ms 972 KB Correct: 3417 out of 12000 queries used.
9 Correct 2 ms 844 KB Correct: 4107 out of 12000 queries used.
10 Correct 2 ms 716 KB Correct: 2608 out of 12000 queries used.

Subtask #5
38.47 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Correct: 2781 out of 500000 queries used.
2 Correct 4 ms 4684 KB Correct: 2896 out of 500000 queries used.
3 Correct 5 ms 6732 KB Correct: 5065 out of 500000 queries used.
4 Correct 5 ms 7500 KB Correct: 5831 out of 500000 queries used.
5 Correct 4 ms 2252 KB Correct: 4765 out of 500000 queries used.
6 Correct 2 ms 972 KB Correct: 4054 out of 500000 queries used.
7 Correct 4 ms 4672 KB Correct: 3759 out of 500000 queries used.
8 Correct 7 ms 6732 KB Correct: 4800 out of 500000 queries used.
9 Correct 7 ms 7500 KB Correct: 5240 out of 500000 queries used.
10 Correct 4 ms 2380 KB Correct: 4174 out of 500000 queries used.
11 Correct 3 ms 844 KB Correct: 2604 out of 12000 queries used.
12 Correct 2 ms 844 KB Correct: 2743 out of 12000 queries used.
13 Correct 2 ms 716 KB Correct: 2626 out of 12000 queries used.
14 Correct 2 ms 972 KB Correct: 4226 out of 12000 queries used.
15 Correct 3 ms 844 KB Correct: 3715 out of 12000 queries used.
16 Correct 3 ms 1072 KB Correct: 3996 out of 12000 queries used.
17 Correct 2 ms 844 KB Correct: 3646 out of 12000 queries used.
18 Correct 2 ms 972 KB Correct: 3417 out of 12000 queries used.
19 Correct 2 ms 844 KB Correct: 4107 out of 12000 queries used.
20 Correct 2 ms 716 KB Correct: 2608 out of 12000 queries used.
21 Correct 2 ms 844 KB Correct: 3460 out of 25000 queries used.
22 Correct 4 ms 4940 KB Correct: 4315 out of 25000 queries used.
23 Correct 4 ms 4684 KB Correct: 2770 out of 25000 queries used.
24 Correct 5 ms 4944 KB Correct: 4429 out of 25000 queries used.
25 Correct 6 ms 6860 KB Correct: 5616 out of 25000 queries used.
26 Correct 6 ms 6860 KB Correct: 5159 out of 25000 queries used.
27 Correct 5 ms 6732 KB Correct: 5011 out of 25000 queries used.
28 Correct 5 ms 6732 KB Correct: 4961 out of 25000 queries used.
29 Correct 5 ms 6740 KB Correct: 4716 out of 25000 queries used.
30 Correct 8 ms 6860 KB Correct: 5394 out of 25000 queries used.
31 Correct 6 ms 7500 KB Correct: 5171 out of 25000 queries used.
32 Correct 2 ms 844 KB Correct: 3222 out of 25000 queries used.
33 Correct 5 ms 7500 KB Correct: 5333 out of 25000 queries used.
34 Correct 7 ms 7628 KB Correct: 6780 out of 25000 queries used.
35 Correct 6 ms 7500 KB Correct: 5257 out of 25000 queries used.
36 Correct 6 ms 7500 KB Correct: 5421 out of 25000 queries used.
37 Correct 6 ms 7500 KB Correct: 5245 out of 25000 queries used.
38 Correct 6 ms 7380 KB Correct: 5380 out of 25000 queries used.
39 Correct 6 ms 7500 KB Correct: 5430 out of 25000 queries used.
40 Correct 6 ms 7560 KB Correct: 6035 out of 25000 queries used.
41 Correct 5 ms 7548 KB Correct: 5278 out of 25000 queries used.
42 Correct 6 ms 7504 KB Correct: 5231 out of 25000 queries used.
43 Correct 2 ms 844 KB Correct: 4044 out of 25000 queries used.
44 Correct 5 ms 7372 KB Correct: 5131 out of 25000 queries used.
45 Correct 7 ms 7500 KB Correct: 6020 out of 25000 queries used.
46 Correct 6 ms 7500 KB Correct: 5167 out of 25000 queries used.
47 Correct 6 ms 7500 KB Correct: 5426 out of 25000 queries used.
48 Correct 6 ms 7504 KB Correct: 5873 out of 25000 queries used.
49 Correct 6 ms 7500 KB Correct: 5290 out of 25000 queries used.
50 Correct 6 ms 7628 KB Correct: 5398 out of 25000 queries used.
51 Correct 6 ms 7500 KB Correct: 5403 out of 25000 queries used.
52 Correct 6 ms 7628 KB Correct: 6095 out of 25000 queries used.
53 Correct 5 ms 7500 KB Correct: 5182 out of 25000 queries used.
54 Correct 4 ms 4812 KB Correct: 3576 out of 25000 queries used.
55 Correct 8 ms 7500 KB Correct: 5260 out of 25000 queries used.
56 Correct 6 ms 7500 KB Correct: 5260 out of 25000 queries used.
57 Correct 6 ms 7628 KB Correct: 6219 out of 25000 queries used.
58 Correct 5 ms 7524 KB Correct: 6031 out of 25000 queries used.
59 Correct 5 ms 7372 KB Correct: 5144 out of 25000 queries used.
60 Correct 3 ms 2252 KB Correct: 4534 out of 25000 queries used.
61 Correct 3 ms 2380 KB Correct: 4375 out of 25000 queries used.
62 Correct 4 ms 2508 KB Correct: 4959 out of 25000 queries used.
63 Correct 4 ms 2508 KB Correct: 4389 out of 25000 queries used.
64 Correct 3 ms 2508 KB Correct: 3851 out of 25000 queries used.
65 Correct 4 ms 4684 KB Correct: 2731 out of 25000 queries used.
66 Correct 3 ms 2380 KB Correct: 4260 out of 25000 queries used.
67 Correct 4 ms 4684 KB Correct: 3602 out of 25000 queries used.
68 Correct 4 ms 4684 KB Correct: 2942 out of 25000 queries used.
69 Correct 4 ms 4684 KB Correct: 2858 out of 25000 queries used.
70 Correct 5 ms 4812 KB Correct: 3087 out of 25000 queries used.