oj.uz

Submission #426454

# Submission time Handle Problem Language Result Execution time Memory
426454 2021-06-14T04:12:51 Z Amylopectin City Mapping (NOI18_citymapping) C++14
73.33 / 100
 14 ms 7552 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;
        }
    }
    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);
    }
    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 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:116:11: warning: unused variable 'j' [-Wunused-variable]
  116 |     int i,j,stn = (rand() % n) + 1;
      |           ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Correct: 2414 out of 500000 queries used.
2 Correct 3 ms 4556 KB Correct: 2292 out of 500000 queries used.
3 Correct 4 ms 5836 KB Correct: 4838 out of 500000 queries used.
4 Correct 6 ms 7372 KB Correct: 4942 out of 500000 queries used.
5 Correct 2 ms 1356 KB Correct: 2933 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Correct: 2414 out of 500000 queries used.
2 Correct 3 ms 4556 KB Correct: 2292 out of 500000 queries used.
3 Correct 4 ms 5836 KB Correct: 4838 out of 500000 queries used.
4 Correct 6 ms 7372 KB Correct: 4942 out of 500000 queries used.
5 Correct 2 ms 1356 KB Correct: 2933 out of 500000 queries used.
6 Correct 2 ms 588 KB Correct: 2305 out of 500000 queries used.
7 Correct 5 ms 5580 KB Correct: 5430 out of 500000 queries used.
8 Correct 5 ms 5964 KB Correct: 4230 out of 500000 queries used.
9 Correct 6 ms 7500 KB Correct: 4947 out of 500000 queries used.
10 Correct 3 ms 1484 KB Correct: 4604 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Correct: 2226 out of 12000 queries used.
2 Correct 2 ms 588 KB Correct: 2228 out of 12000 queries used.
3 Correct 2 ms 588 KB Correct: 2143 out of 12000 queries used.
4 Correct 2 ms 588 KB Correct: 2443 out of 12000 queries used.
5 Correct 2 ms 588 KB Correct: 2406 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Correct: 2226 out of 12000 queries used.
2 Correct 2 ms 588 KB Correct: 2228 out of 12000 queries used.
3 Correct 2 ms 588 KB Correct: 2143 out of 12000 queries used.
4 Correct 2 ms 588 KB Correct: 2443 out of 12000 queries used.
5 Correct 2 ms 588 KB Correct: 2406 out of 12000 queries used.
6 Correct 2 ms 588 KB Correct: 2201 out of 12000 queries used.
7 Correct 2 ms 588 KB Correct: 2156 out of 12000 queries used.
8 Correct 2 ms 588 KB Correct: 2389 out of 12000 queries used.
9 Correct 2 ms 588 KB Correct: 2239 out of 12000 queries used.
10 Correct 2 ms 588 KB Correct: 2047 out of 12000 queries used.

Subtask #5
16.33 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Correct: 2414 out of 500000 queries used.
2 Correct 3 ms 4556 KB Correct: 2292 out of 500000 queries used.
3 Correct 4 ms 5836 KB Correct: 4838 out of 500000 queries used.
4 Correct 6 ms 7372 KB Correct: 4942 out of 500000 queries used.
5 Correct 2 ms 1356 KB Correct: 2933 out of 500000 queries used.
6 Correct 2 ms 588 KB Correct: 2305 out of 500000 queries used.
7 Correct 5 ms 5580 KB Correct: 5430 out of 500000 queries used.
8 Correct 5 ms 5964 KB Correct: 4230 out of 500000 queries used.
9 Correct 6 ms 7500 KB Correct: 4947 out of 500000 queries used.
10 Correct 3 ms 1484 KB Correct: 4604 out of 500000 queries used.
11 Correct 2 ms 588 KB Correct: 2226 out of 12000 queries used.
12 Correct 2 ms 588 KB Correct: 2228 out of 12000 queries used.
13 Correct 2 ms 588 KB Correct: 2143 out of 12000 queries used.
14 Correct 2 ms 588 KB Correct: 2443 out of 12000 queries used.
15 Correct 2 ms 588 KB Correct: 2406 out of 12000 queries used.
16 Correct 2 ms 588 KB Correct: 2201 out of 12000 queries used.
17 Correct 2 ms 588 KB Correct: 2156 out of 12000 queries used.
18 Correct 2 ms 588 KB Correct: 2389 out of 12000 queries used.
19 Correct 2 ms 588 KB Correct: 2239 out of 12000 queries used.
20 Correct 2 ms 588 KB Correct: 2047 out of 12000 queries used.
21 Correct 2 ms 588 KB Correct: 2329 out of 25000 queries used.
22 Correct 4 ms 4940 KB Correct: 4853 out of 25000 queries used.
23 Correct 5 ms 4556 KB Correct: 1996 out of 25000 queries used.
24 Correct 4 ms 4812 KB Correct: 3843 out of 25000 queries used.
25 Correct 5 ms 6092 KB Correct: 4317 out of 25000 queries used.
26 Correct 7 ms 6064 KB Correct: 4466 out of 25000 queries used.
27 Correct 5 ms 5836 KB Correct: 4160 out of 25000 queries used.
28 Correct 6 ms 5840 KB Correct: 4402 out of 25000 queries used.
29 Correct 5 ms 5964 KB Correct: 4862 out of 25000 queries used.
30 Correct 8 ms 5860 KB Correct: 4306 out of 25000 queries used.
31 Correct 6 ms 7500 KB Correct: 4964 out of 25000 queries used.
32 Correct 2 ms 588 KB Correct: 2326 out of 25000 queries used.
33 Correct 6 ms 7372 KB Correct: 4938 out of 25000 queries used.
34 Correct 5 ms 7552 KB Correct: 4990 out of 25000 queries used.
35 Correct 5 ms 7372 KB Correct: 4948 out of 25000 queries used.
36 Correct 6 ms 7500 KB Correct: 4961 out of 25000 queries used.
37 Correct 7 ms 7500 KB Correct: 4941 out of 25000 queries used.
38 Correct 7 ms 7500 KB Correct: 5200 out of 25000 queries used.
39 Correct 6 ms 7372 KB Correct: 4940 out of 25000 queries used.
40 Correct 6 ms 7500 KB Correct: 4947 out of 25000 queries used.
41 Correct 6 ms 7372 KB Correct: 4945 out of 25000 queries used.
42 Correct 6 ms 7500 KB Correct: 5016 out of 25000 queries used.
43 Correct 2 ms 716 KB Correct: 2087 out of 25000 queries used.
44 Correct 14 ms 7380 KB Correct: 4891 out of 25000 queries used.
45 Correct 5 ms 7372 KB Correct: 4922 out of 25000 queries used.
46 Correct 5 ms 7500 KB Correct: 5181 out of 25000 queries used.
47 Correct 5 ms 7372 KB Correct: 4940 out of 25000 queries used.
48 Correct 7 ms 7372 KB Correct: 4947 out of 25000 queries used.
49 Correct 7 ms 7500 KB Correct: 5008 out of 25000 queries used.
50 Correct 6 ms 7512 KB Correct: 4957 out of 25000 queries used.
51 Correct 7 ms 7508 KB Correct: 4988 out of 25000 queries used.
52 Correct 8 ms 7508 KB Correct: 4944 out of 25000 queries used.
53 Correct 8 ms 7508 KB Correct: 5227 out of 25000 queries used.
54 Correct 6 ms 5204 KB Correct: 7408 out of 25000 queries used.
55 Correct 7 ms 7244 KB Correct: 4965 out of 25000 queries used.
56 Correct 5 ms 7500 KB Correct: 4946 out of 25000 queries used.
57 Correct 5 ms 7500 KB Correct: 5229 out of 25000 queries used.
58 Correct 6 ms 7384 KB Correct: 4898 out of 25000 queries used.
59 Correct 7 ms 7416 KB Correct: 4929 out of 25000 queries used.
60 Correct 2 ms 1484 KB Correct: 3320 out of 25000 queries used.
61 Correct 2 ms 1612 KB Correct: 5780 out of 25000 queries used.
62 Correct 3 ms 1492 KB Correct: 3113 out of 25000 queries used.
63 Correct 3 ms 1612 KB Correct: 5789 out of 25000 queries used.
64 Correct 3 ms 1484 KB Correct: 5791 out of 25000 queries used.
65 Correct 5 ms 4684 KB Correct: 2354 out of 25000 queries used.
66 Correct 3 ms 1484 KB Correct: 3175 out of 25000 queries used.
67 Correct 4 ms 4692 KB Correct: 3129 out of 25000 queries used.
68 Correct 4 ms 4812 KB Correct: 2890 out of 25000 queries used.
69 Correct 6 ms 4984 KB Correct: 10839 out of 25000 queries used.
70 Correct 4 ms 5196 KB Correct: 5469 out of 25000 queries used.