oj.uz

Submission #939297

# Submission time Handle Problem Language Result Execution time Memory
939297 2024-03-06T08:21:09 Z fdnfksd City Mapping (NOI18_citymapping) C++14
57 / 100
 44 ms 10864 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
pli cc[maxn];
ll dis[1005][1005];
ll d[maxn];
static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
static long long dist[1005];
static vector< pair<int, int> > adjlist[1005];
static vector< pair< pair<int, int>, int > > edgelist, user_edgelist;

/*static void dfs(int x, int p, long long d, int dep) {
	dist[x] = d;
	depth[x] = dep;
	twok[x][0] = p;
	for (int i = 1; i <= 10; i++) {
		if (twok[x][i - 1] == -1) break;
		twok[x][i] = twok[twok[x][i - 1]][i - 1];
	}
	for (int i = 0; i < (int)adjlist[x].size(); i++) {
		if (adjlist[x][i].first == p) continue;
		dfs(adjlist[x][i].first, x, d + adjlist[x][i].second, dep + 1);
	}
}

static int lca(int x, int y) {
	if (depth[x] > depth[y]) swap(x, y);
	int dd = depth[y] - depth[x];
	for (int i = 0; i <= 10; i++) if (dd & (1 << i)) y = twok[y][i];
	if (x == y) return x;
	for (int i = 10; i >= 0; i--) {
		if (twok[x][i] != twok[y][i]) {
			x = twok[x][i];
			y = twok[y][i];
		}
	}
	return twok[x][0];
}

long long get_distance(int X, int Y) {
	if (X <= 0 || X > N || Y <= 0 || Y > N) {
		printf("Wrong Answer: get_distance() arguments out of range.\n");
		exit(0);
	}
	curQ++;
	if (curQ > Q) {
		printf("Wrong Answer: Too many calls to get_distance().\n");
		exit(0);
	}
	return dist[X-1] + dist[Y-1] - dist[lca(X-1, Y-1)] * 2;
}
*/
void find_roads(int N, int Q, int A[], int B[], int W[])
{
    ll n=N,q=Q;
    if(q==(ll)5e5)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                dis[i][j]=get_distance(i,j);
                dis[j][i]=dis[i][j];
            }
        }
        for(int i=2;i<=n;i++)
        {
            ll luu=1;
            for(int j=1;j<=n;j++)
            {
                if(i==j) continue;
                if(dis[i][1]==dis[j][1]+dis[i][j])
                {
                    if(dis[i][luu]>dis[i][j]) luu=j;
                    //cout << luu << '\n';
                }
            }
            A[i-2]=i;
            B[i-2]=luu;
            W[i-2]=dis[i][luu];
        }
    }
    else
    {
        ll luu=1;
        for(int i=1;i<=n;i++)
        {
            d[i]=get_distance(i,1);
            if(d[i]>d[luu]) luu=i;
        }
        vector<pli>cc;
        for(int i=1;i<=n;i++)
        {
            cc.pb({get_distance(i,luu),(ll)i});
        }
        sort(cc.begin(),cc.end());
        for(int i=1;i<cc.size();i++)
        {
            A[i-1]=cc[i].se;
            B[i-1]=cc[i-1].se;
            W[i-1]=cc[i].fi-cc[i-1].fi;
        }
    }
}

/*int main() {
	if (scanf("%d%d%d", &N, &Q, &S) != 3) {
		printf("Wrong Input Format\n");
		exit(0);
	}
	for (int i = 0; i < N - 1; i++) {
		int a, b, w;
		if (scanf("%d%d%d", &a, &b, &w) != 3) {
			printf("Wrong Input Format\n");
			return 0;
		}
		a--;
		b--;
		adjlist[a].push_back(make_pair(b, w));
		adjlist[b].push_back(make_pair(a, w));
		edgelist.push_back(make_pair(make_pair(min(a, b) + 1, max(a, b) + 1), w));
	}
	sort(edgelist.begin(), edgelist.end());
	memset(twok, -1, sizeof(twok));
	dfs(0, -1, 0, 0);
	int A[N-1], B[N-1], W[N-1];
	memset(A, 0, sizeof(A));
	memset(B, 0, sizeof(B));
	memset(W, 0, sizeof(W));
	find_roads(N, Q, A, B, W);
	for (int i = 0; i < N-1; i++) user_edgelist.push_back(make_pair(make_pair(min(A[i], B[i]), max(A[i], B[i])), W[i]));
	sort(user_edgelist.begin(), user_edgelist.end());
	if (edgelist != user_edgelist) {
		printf("Wrong Answer: Reported list of edges differ from actual.\n");
		exit(0);
	}
	if (S <= 4) {
		printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q);
		exit(0);
	} else {
		if (curQ <= target) printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q);
		else if (curQ >= 12000) printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (10.0-10.0*((double)(curQ - 12000) / 13000)) / 43 * 100, curQ, Q);
		else printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (40.0-30.0*((double)(curQ - target) / (12000 - target))) / 43 * 100, curQ, Q);
	}
}*/

Compilation message

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int i=1;i<cc.size();i++)
      |                     ~^~~~~~~~~~
citymapping.cpp: At global scope:
citymapping.cpp:17:18: warning: 'dist' defined but not used [-Wunused-variable]
   17 | static long long dist[1005];
      |                  ^~~~
citymapping.cpp:16:56: warning: 'target' defined but not used [-Wunused-variable]
   16 | static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
      |                                                        ^~~~~~
citymapping.cpp:16:50: warning: 'curQ' defined but not used [-Wunused-variable]
   16 | static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
      |                                                  ^~~~
citymapping.cpp:16:37: warning: 'depth' defined but not used [-Wunused-variable]
   16 | static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
      |                                     ^~~~~
citymapping.cpp:16:21: warning: 'twok' defined but not used [-Wunused-variable]
   16 | static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
      |                     ^~~~
citymapping.cpp:16:18: warning: 'S' defined but not used [-Wunused-variable]
   16 | static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
      |                  ^
citymapping.cpp:16:15: warning: 'Q' defined but not used [-Wunused-variable]
   16 | static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
      |               ^
citymapping.cpp:16:12: warning: 'N' defined but not used [-Wunused-variable]
   16 | static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
      |            ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 10844 KB Correct: 498501 out of 500000 queries used.
2 Correct 35 ms 10864 KB Correct: 499500 out of 500000 queries used.
3 Correct 28 ms 10860 KB Correct: 492528 out of 500000 queries used.
4 Correct 24 ms 10844 KB Correct: 494515 out of 500000 queries used.
5 Correct 35 ms 10844 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 10844 KB Correct: 498501 out of 500000 queries used.
2 Correct 35 ms 10864 KB Correct: 499500 out of 500000 queries used.
3 Correct 28 ms 10860 KB Correct: 492528 out of 500000 queries used.
4 Correct 24 ms 10844 KB Correct: 494515 out of 500000 queries used.
5 Correct 35 ms 10844 KB Correct: 498501 out of 500000 queries used.
6 Correct 32 ms 10840 KB Correct: 495510 out of 500000 queries used.
7 Correct 41 ms 10864 KB Correct: 497503 out of 500000 queries used.
8 Correct 28 ms 10856 KB Correct: 497503 out of 500000 queries used.
9 Correct 24 ms 10844 KB Correct: 495510 out of 500000 queries used.
10 Correct 36 ms 10844 KB Correct: 496506 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Correct: 1982 out of 12000 queries used.
2 Correct 1 ms 604 KB Correct: 1986 out of 12000 queries used.
3 Correct 1 ms 604 KB Correct: 2000 out of 12000 queries used.
4 Correct 1 ms 604 KB Correct: 1986 out of 12000 queries used.
5 Correct 1 ms 604 KB Correct: 1982 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Correct: 1982 out of 12000 queries used.
2 Correct 1 ms 604 KB Correct: 1986 out of 12000 queries used.
3 Correct 1 ms 604 KB Correct: 2000 out of 12000 queries used.
4 Correct 1 ms 604 KB Correct: 1986 out of 12000 queries used.
5 Correct 1 ms 604 KB Correct: 1982 out of 12000 queries used.
6 Correct 2 ms 604 KB Correct: 1996 out of 12000 queries used.
7 Correct 1 ms 600 KB Correct: 1992 out of 12000 queries used.
8 Correct 1 ms 604 KB Correct: 2000 out of 12000 queries used.
9 Correct 1 ms 604 KB Correct: 1994 out of 12000 queries used.
10 Correct 1 ms 604 KB Correct: 1988 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 10844 KB Correct: 498501 out of 500000 queries used.
2 Correct 35 ms 10864 KB Correct: 499500 out of 500000 queries used.
3 Correct 28 ms 10860 KB Correct: 492528 out of 500000 queries used.
4 Correct 24 ms 10844 KB Correct: 494515 out of 500000 queries used.
5 Correct 35 ms 10844 KB Correct: 498501 out of 500000 queries used.
6 Correct 32 ms 10840 KB Correct: 495510 out of 500000 queries used.
7 Correct 41 ms 10864 KB Correct: 497503 out of 500000 queries used.
8 Correct 28 ms 10856 KB Correct: 497503 out of 500000 queries used.
9 Correct 24 ms 10844 KB Correct: 495510 out of 500000 queries used.
10 Correct 36 ms 10844 KB Correct: 496506 out of 500000 queries used.
11 Correct 1 ms 600 KB Correct: 1982 out of 12000 queries used.
12 Correct 1 ms 604 KB Correct: 1986 out of 12000 queries used.
13 Correct 1 ms 604 KB Correct: 2000 out of 12000 queries used.
14 Correct 1 ms 604 KB Correct: 1986 out of 12000 queries used.
15 Correct 1 ms 604 KB Correct: 1982 out of 12000 queries used.
16 Correct 2 ms 604 KB Correct: 1996 out of 12000 queries used.
17 Correct 1 ms 600 KB Correct: 1992 out of 12000 queries used.
18 Correct 1 ms 604 KB Correct: 2000 out of 12000 queries used.
19 Correct 1 ms 604 KB Correct: 1994 out of 12000 queries used.
20 Correct 1 ms 604 KB Correct: 1988 out of 12000 queries used.
21 Correct 1 ms 604 KB Correct: 1992 out of 25000 queries used.
22 Incorrect 1 ms 604 KB Reported list of edges differ from actual.
23 Halted 0 ms 0 KB -