oj.uz

Submission #426459

# Submission time Handle Problem Language Result Execution time Memory
426459 2021-06-14T04:18:06 Z Amylopectin City Mapping (NOI18_citymapping) C++14
100 / 100
 9 ms 7500 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 = (cli[cn] * 2) / 3;
    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:120:11: warning: unused variable 'j' [-Wunused-variable]
  120 |     int i,j,stn = (rand() % n) + 1;
      |           ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Correct: 2910 out of 500000 queries used.
2 Correct 3 ms 4684 KB Correct: 2829 out of 500000 queries used.
3 Correct 7 ms 6732 KB Correct: 6264 out of 500000 queries used.
4 Correct 6 ms 7372 KB Correct: 5242 out of 500000 queries used.
5 Correct 4 ms 2508 KB Correct: 4672 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Correct: 2910 out of 500000 queries used.
2 Correct 3 ms 4684 KB Correct: 2829 out of 500000 queries used.
3 Correct 7 ms 6732 KB Correct: 6264 out of 500000 queries used.
4 Correct 6 ms 7372 KB Correct: 5242 out of 500000 queries used.
5 Correct 4 ms 2508 KB Correct: 4672 out of 500000 queries used.
6 Correct 2 ms 844 KB Correct: 3763 out of 500000 queries used.
7 Correct 3 ms 4684 KB Correct: 4027 out of 500000 queries used.
8 Correct 5 ms 6860 KB Correct: 5201 out of 500000 queries used.
9 Correct 5 ms 7372 KB Correct: 5516 out of 500000 queries used.
10 Correct 4 ms 2508 KB Correct: 4816 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 844 KB Correct: 2816 out of 12000 queries used.
2 Correct 2 ms 972 KB Correct: 4065 out of 12000 queries used.
3 Correct 2 ms 844 KB Correct: 3766 out of 12000 queries used.
4 Correct 2 ms 844 KB Correct: 2801 out of 12000 queries used.
5 Correct 2 ms 716 KB Correct: 3068 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 844 KB Correct: 2816 out of 12000 queries used.
2 Correct 2 ms 972 KB Correct: 4065 out of 12000 queries used.
3 Correct 2 ms 844 KB Correct: 3766 out of 12000 queries used.
4 Correct 2 ms 844 KB Correct: 2801 out of 12000 queries used.
5 Correct 2 ms 716 KB Correct: 3068 out of 12000 queries used.
6 Correct 2 ms 716 KB Correct: 2933 out of 12000 queries used.
7 Correct 2 ms 716 KB Correct: 2290 out of 12000 queries used.
8 Correct 2 ms 716 KB Correct: 2688 out of 12000 queries used.
9 Correct 2 ms 716 KB Correct: 3579 out of 12000 queries used.
10 Correct 2 ms 716 KB Correct: 2958 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Correct: 2910 out of 500000 queries used.
2 Correct 3 ms 4684 KB Correct: 2829 out of 500000 queries used.
3 Correct 7 ms 6732 KB Correct: 6264 out of 500000 queries used.
4 Correct 6 ms 7372 KB Correct: 5242 out of 500000 queries used.
5 Correct 4 ms 2508 KB Correct: 4672 out of 500000 queries used.
6 Correct 2 ms 844 KB Correct: 3763 out of 500000 queries used.
7 Correct 3 ms 4684 KB Correct: 4027 out of 500000 queries used.
8 Correct 5 ms 6860 KB Correct: 5201 out of 500000 queries used.
9 Correct 5 ms 7372 KB Correct: 5516 out of 500000 queries used.
10 Correct 4 ms 2508 KB Correct: 4816 out of 500000 queries used.
11 Correct 5 ms 844 KB Correct: 2816 out of 12000 queries used.
12 Correct 2 ms 972 KB Correct: 4065 out of 12000 queries used.
13 Correct 2 ms 844 KB Correct: 3766 out of 12000 queries used.
14 Correct 2 ms 844 KB Correct: 2801 out of 12000 queries used.
15 Correct 2 ms 716 KB Correct: 3068 out of 12000 queries used.
16 Correct 2 ms 716 KB Correct: 2933 out of 12000 queries used.
17 Correct 2 ms 716 KB Correct: 2290 out of 12000 queries used.
18 Correct 2 ms 716 KB Correct: 2688 out of 12000 queries used.
19 Correct 2 ms 716 KB Correct: 3579 out of 12000 queries used.
20 Correct 2 ms 716 KB Correct: 2958 out of 12000 queries used.
21 Correct 2 ms 844 KB Correct: 3649 out of 25000 queries used.
22 Correct 3 ms 4812 KB Correct: 2860 out of 25000 queries used.
23 Correct 4 ms 4684 KB Correct: 3052 out of 25000 queries used.
24 Correct 4 ms 4684 KB Correct: 2920 out of 25000 queries used.
25 Correct 8 ms 6860 KB Correct: 5798 out of 25000 queries used.
26 Correct 6 ms 6724 KB Correct: 5135 out of 25000 queries used.
27 Correct 5 ms 6732 KB Correct: 5501 out of 25000 queries used.
28 Correct 6 ms 6784 KB Correct: 5113 out of 25000 queries used.
29 Correct 6 ms 6732 KB Correct: 5719 out of 25000 queries used.
30 Correct 6 ms 6860 KB Correct: 5188 out of 25000 queries used.
31 Correct 7 ms 7472 KB Correct: 5139 out of 25000 queries used.
32 Correct 2 ms 844 KB Correct: 3260 out of 25000 queries used.
33 Correct 7 ms 7372 KB Correct: 5338 out of 25000 queries used.
34 Correct 6 ms 7500 KB Correct: 5223 out of 25000 queries used.
35 Correct 5 ms 7500 KB Correct: 6368 out of 25000 queries used.
36 Correct 7 ms 7372 KB Correct: 5501 out of 25000 queries used.
37 Correct 7 ms 7372 KB Correct: 5400 out of 25000 queries used.
38 Correct 9 ms 7480 KB Correct: 6027 out of 25000 queries used.
39 Correct 7 ms 7476 KB Correct: 6050 out of 25000 queries used.
40 Correct 7 ms 7372 KB Correct: 5204 out of 25000 queries used.
41 Correct 5 ms 7500 KB Correct: 5226 out of 25000 queries used.
42 Correct 6 ms 7372 KB Correct: 5301 out of 25000 queries used.
43 Correct 2 ms 716 KB Correct: 3652 out of 25000 queries used.
44 Correct 5 ms 7372 KB Correct: 6034 out of 25000 queries used.
45 Correct 5 ms 7244 KB Correct: 5212 out of 25000 queries used.
46 Correct 5 ms 7500 KB Correct: 5146 out of 25000 queries used.
47 Correct 6 ms 7500 KB Correct: 5226 out of 25000 queries used.
48 Correct 6 ms 7372 KB Correct: 5175 out of 25000 queries used.
49 Correct 5 ms 7372 KB Correct: 5596 out of 25000 queries used.
50 Correct 8 ms 7372 KB Correct: 5276 out of 25000 queries used.
51 Correct 6 ms 7500 KB Correct: 5202 out of 25000 queries used.
52 Correct 6 ms 7500 KB Correct: 5206 out of 25000 queries used.
53 Correct 5 ms 7500 KB Correct: 5497 out of 25000 queries used.
54 Correct 3 ms 4684 KB Correct: 3040 out of 25000 queries used.
55 Correct 6 ms 7372 KB Correct: 5229 out of 25000 queries used.
56 Correct 6 ms 7372 KB Correct: 5416 out of 25000 queries used.
57 Correct 5 ms 7372 KB Correct: 5217 out of 25000 queries used.
58 Correct 5 ms 7372 KB Correct: 5135 out of 25000 queries used.
59 Correct 5 ms 7372 KB Correct: 5268 out of 25000 queries used.
60 Correct 3 ms 2380 KB Correct: 5098 out of 25000 queries used.
61 Correct 4 ms 2252 KB Correct: 4368 out of 25000 queries used.
62 Correct 4 ms 2380 KB Correct: 4495 out of 25000 queries used.
63 Correct 4 ms 2380 KB Correct: 4477 out of 25000 queries used.
64 Correct 3 ms 2380 KB Correct: 5209 out of 25000 queries used.
65 Correct 4 ms 4812 KB Correct: 3021 out of 25000 queries used.
66 Correct 4 ms 2252 KB Correct: 3989 out of 25000 queries used.
67 Correct 4 ms 4684 KB Correct: 3480 out of 25000 queries used.
68 Correct 3 ms 4556 KB Correct: 2802 out of 25000 queries used.
69 Correct 3 ms 4684 KB Correct: 2327 out of 25000 queries used.
70 Correct 4 ms 4556 KB Correct: 2536 out of 25000 queries used.