oj.uz

Submission #147504

# Submission time Handle Problem Language Result Execution time Memory
147504 2019-08-29T20:01:25 Z JovanK26 City Mapping (NOI18_citymapping) C++14
57 / 100
 140 ms 9956 KB 
#include "citymapping.h"
#include<bits/stdc++.h>
using namespace std;
struct edge
{
    int a;
    int b;
    long long w;
};
vector<edge> edg;
bool cmp(edge i,edge j)
{
    return i.w<j.w;
}
bool vis[1001][1001];
int prt[1001];
int sz[1001];
int findd(int x)
{
    while(prt[x]!=x)
    {
        x=prt[x];
    }
    return x;
}
void unionn(int x,int y)
{
    x=findd(x);
    y=findd(y);
    if(sz[x]<sz[y])swap(x,y);
    prt[y]=x;
    sz[x]+=sz[y];
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
    int br=0;
    if(Q==500000)
    {
        for(int i=0;i<=N;i++)
    {
        prt[i]=i;
        sz[i]=1;
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(i==j)continue;
            if(vis[i][j] || vis[j][i])continue;
            vis[i][j]=1;
            vis[j][i]=1;
            long long temp=get_distance(i,j);
            edge tmp;
            tmp.a=i;
            tmp.b=j;
            tmp.w=temp;
            edg.push_back(tmp);
        }
    }
    sort(edg.begin(),edg.end(),cmp);
    for(int i=0;i<edg.size();i++)
    {
        if(findd(edg[i].a)!=findd(edg[i].b))
        {
            unionn(edg[i].a,edg[i].b);
            A[br]=edg[i].a;
            B[br]=edg[i].b;
            W[br]=edg[i].w;
            br++;
        }
    }
    }
    else
    {
       int nd=-1;
       long long d=0;
       for(int i=2;i<=N;i++)
       {
           long long qry=get_distance(1,i);
           if(qry>d)
           {
               d=qry;
               nd=i;
           }
       }
       vector< pair<long long,int> > v;
       for(int i=1;i<=N;i++)
       {
           if(i==nd)continue;
           v.push_back(make_pair(get_distance(nd,i),i));
       }
       sort(v.begin(),v.end());
       int prev=nd;
       long long prevd=0;
       for(int i=0;i<v.size();i++)
       {
           A[br]=prev;
           B[br]=v[i].second;
           W[br]=v[i].first-prevd;
           prev=v[i].second;
           prevd=v[i].first;
           br++;
       }
    }
	return;
}

Compilation message

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<edg.size();i++)
                 ~^~~~~~~~~~~
citymapping.cpp:94:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int i=0;i<v.size();i++)
                    ~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 9820 KB Correct: 498501 out of 500000 queries used.
2 Correct 119 ms 9820 KB Correct: 499500 out of 500000 queries used.
3 Correct 95 ms 9820 KB Correct: 492528 out of 500000 queries used.
4 Correct 92 ms 9820 KB Correct: 494515 out of 500000 queries used.
5 Correct 112 ms 9820 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 9820 KB Correct: 498501 out of 500000 queries used.
2 Correct 119 ms 9820 KB Correct: 499500 out of 500000 queries used.
3 Correct 95 ms 9820 KB Correct: 492528 out of 500000 queries used.
4 Correct 92 ms 9820 KB Correct: 494515 out of 500000 queries used.
5 Correct 112 ms 9820 KB Correct: 498501 out of 500000 queries used.
6 Correct 134 ms 9820 KB Correct: 495510 out of 500000 queries used.
7 Correct 135 ms 9864 KB Correct: 497503 out of 500000 queries used.
8 Correct 132 ms 9820 KB Correct: 497503 out of 500000 queries used.
9 Correct 126 ms 9736 KB Correct: 495510 out of 500000 queries used.
10 Correct 140 ms 9956 KB Correct: 496506 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Correct: 1980 out of 12000 queries used.
2 Correct 3 ms 504 KB Correct: 1984 out of 12000 queries used.
3 Correct 3 ms 504 KB Correct: 1998 out of 12000 queries used.
4 Correct 3 ms 504 KB Correct: 1984 out of 12000 queries used.
5 Correct 3 ms 504 KB Correct: 1980 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Correct: 1980 out of 12000 queries used.
2 Correct 3 ms 504 KB Correct: 1984 out of 12000 queries used.
3 Correct 3 ms 504 KB Correct: 1998 out of 12000 queries used.
4 Correct 3 ms 504 KB Correct: 1984 out of 12000 queries used.
5 Correct 3 ms 504 KB Correct: 1980 out of 12000 queries used.
6 Correct 3 ms 504 KB Correct: 1994 out of 12000 queries used.
7 Correct 3 ms 472 KB Correct: 1990 out of 12000 queries used.
8 Correct 3 ms 504 KB Correct: 1998 out of 12000 queries used.
9 Correct 3 ms 504 KB Correct: 1992 out of 12000 queries used.
10 Correct 3 ms 504 KB Correct: 1986 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 9820 KB Correct: 498501 out of 500000 queries used.
2 Correct 119 ms 9820 KB Correct: 499500 out of 500000 queries used.
3 Correct 95 ms 9820 KB Correct: 492528 out of 500000 queries used.
4 Correct 92 ms 9820 KB Correct: 494515 out of 500000 queries used.
5 Correct 112 ms 9820 KB Correct: 498501 out of 500000 queries used.
6 Correct 134 ms 9820 KB Correct: 495510 out of 500000 queries used.
7 Correct 135 ms 9864 KB Correct: 497503 out of 500000 queries used.
8 Correct 132 ms 9820 KB Correct: 497503 out of 500000 queries used.
9 Correct 126 ms 9736 KB Correct: 495510 out of 500000 queries used.
10 Correct 140 ms 9956 KB Correct: 496506 out of 500000 queries used.
11 Correct 3 ms 504 KB Correct: 1980 out of 12000 queries used.
12 Correct 3 ms 504 KB Correct: 1984 out of 12000 queries used.
13 Correct 3 ms 504 KB Correct: 1998 out of 12000 queries used.
14 Correct 3 ms 504 KB Correct: 1984 out of 12000 queries used.
15 Correct 3 ms 504 KB Correct: 1980 out of 12000 queries used.
16 Correct 3 ms 504 KB Correct: 1994 out of 12000 queries used.
17 Correct 3 ms 472 KB Correct: 1990 out of 12000 queries used.
18 Correct 3 ms 504 KB Correct: 1998 out of 12000 queries used.
19 Correct 3 ms 504 KB Correct: 1992 out of 12000 queries used.
20 Correct 3 ms 504 KB Correct: 1986 out of 12000 queries used.
21 Correct 3 ms 504 KB Correct: 1990 out of 25000 queries used.
22 Incorrect 3 ms 504 KB Reported list of edges differ from actual.
23 Halted 0 ms 0 KB -