# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
147501 | 2019-08-29T19:45:49 Z | JovanK26 | City Mapping (NOI18_citymapping) | C++14 | 134 ms | 7780 KB |
#include "citymapping.h" #include<bits/stdc++.h> using namespace std; struct edge { int a; int b; int 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; 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++; } } return; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 127 ms | 7780 KB | Correct: 498501 out of 500000 queries used. |
2 | Correct | 117 ms | 7780 KB | Correct: 499500 out of 500000 queries used. |
3 | Correct | 94 ms | 7772 KB | Correct: 492528 out of 500000 queries used. |
4 | Correct | 89 ms | 7780 KB | Correct: 494515 out of 500000 queries used. |
5 | Correct | 109 ms | 7780 KB | Correct: 498501 out of 500000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 127 ms | 7780 KB | Correct: 498501 out of 500000 queries used. |
2 | Correct | 117 ms | 7780 KB | Correct: 499500 out of 500000 queries used. |
3 | Correct | 94 ms | 7772 KB | Correct: 492528 out of 500000 queries used. |
4 | Correct | 89 ms | 7780 KB | Correct: 494515 out of 500000 queries used. |
5 | Correct | 109 ms | 7780 KB | Correct: 498501 out of 500000 queries used. |
6 | Incorrect | 134 ms | 7780 KB | Reported list of edges differ from actual. |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 1784 KB | Too many calls to get_distance(). |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 1784 KB | Too many calls to get_distance(). |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 127 ms | 7780 KB | Correct: 498501 out of 500000 queries used. |
2 | Correct | 117 ms | 7780 KB | Correct: 499500 out of 500000 queries used. |
3 | Correct | 94 ms | 7772 KB | Correct: 492528 out of 500000 queries used. |
4 | Correct | 89 ms | 7780 KB | Correct: 494515 out of 500000 queries used. |
5 | Correct | 109 ms | 7780 KB | Correct: 498501 out of 500000 queries used. |
6 | Incorrect | 134 ms | 7780 KB | Reported list of edges differ from actual. |
7 | Halted | 0 ms | 0 KB | - |