oj.uz

Submission #426444

# Submission time Handle Problem Language Result Execution time Memory
426444 2021-06-14T04:03:38 Z Amylopectin City Mapping (NOI18_citymapping) C++14
22 / 100
 6 ms 5592 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
{
    int no,dis;
};
struct pat
{
    int fr,to,dis;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.dis < r.dis;
}
struct pat apa[mxn] = {};
int di[mxn][mxn] = {},li[mxn][mxn] = {},cli[mxn] = {},u[mxn] = {},ncli[mxn] = {},capa = 0;
//struct we fli[mxn] = {};
int re(int cn,int 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;
    }
    int 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;
    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 480 KB Correct: 2414 out of 500000 queries used.
2 Correct 4 ms 4308 KB Correct: 2292 out of 500000 queries used.
3 Correct 3 ms 4684 KB Correct: 4838 out of 500000 queries used.
4 Correct 6 ms 5592 KB Correct: 4942 out of 500000 queries used.
5 Correct 3 ms 1100 KB Correct: 2933 out of 500000 queries used.

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 480 KB Correct: 2414 out of 500000 queries used.
2 Correct 4 ms 4308 KB Correct: 2292 out of 500000 queries used.
3 Correct 3 ms 4684 KB Correct: 4838 out of 500000 queries used.
4 Correct 6 ms 5592 KB Correct: 4942 out of 500000 queries used.
5 Correct 3 ms 1100 KB Correct: 2933 out of 500000 queries used.
6 Incorrect 2 ms 716 KB Reported list of edges differ from actual.
7 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Correct: 2226 out of 12000 queries used.
2 Correct 2 ms 460 KB Correct: 2228 out of 12000 queries used.
3 Correct 2 ms 460 KB Correct: 2143 out of 12000 queries used.
4 Correct 2 ms 472 KB Correct: 2443 out of 12000 queries used.
5 Correct 4 ms 460 KB Correct: 2406 out of 12000 queries used.
6 Incorrect 3 ms 640 KB Reported list of edges differ from actual.
7 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 480 KB Correct: 2414 out of 500000 queries used.
2 Correct 4 ms 4308 KB Correct: 2292 out of 500000 queries used.
3 Correct 3 ms 4684 KB Correct: 4838 out of 500000 queries used.
4 Correct 6 ms 5592 KB Correct: 4942 out of 500000 queries used.
5 Correct 3 ms 1100 KB Correct: 2933 out of 500000 queries used.
6 Incorrect 2 ms 716 KB Reported list of edges differ from actual.
7 Halted 0 ms 0 KB -