oj.uz

Submission #57800

# Submission time Handle Problem Language Result Execution time Memory
57800 2018-07-16T07:41:32 Z alenam0161 Towns (IOI15_towns) C++17
25 / 100
 37 ms 2844 KB 
#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

int f[1107][1107];
int d[1107][1107];
int hubDistance(int N, int sub) {
  	for(int i=0;i<N;++i)
        for(int j=0;j<N;++j){
            f[i][j]=0;
        }
  	auto  dis=[&](int x,int y){
          if(x==y)return 0;
          if(x>y)swap(x,y);
          if(f[x][y]==false){
              f[x][y]=true;
              d[x][y]=getDistance(x,y);
          }
        return d[x][y];
    };
	int x=-1;
	for(int i=1;i<N;++i){
        if(x==-1||dis(0,x)<dis(0,i)){
            x=i;
        }
	}
	int y=-1;
	for(int i=0;i<N;++i){
        if(y==x)continue;
        if(i==x)continue;
        if(y==-1||dis(x,y)<dis(x,i)){
            y=i;
        }
	}
	map<int,int> mp;
	map<int,vector<int>> qan;
	for(int i=0;i<N;++i){
        if(i==x||i==y){
            continue;
        }
        int d1=dis(x,i);
        int d2=dis(y,i);
        int l=dis(x,y);
        int e=d1+d2-l;
        e/=2;
        int v=d2-e;
        mp[v]=max(mp[v],e);
        mp[v]=max(mp[v],d1-e);
        mp[v]=max(mp[v],d2-e);
        qan[v].push_back(i);
	}
	int ans=1e9;
	int hwx=1;
	bool ok=0;
	int hx=N/2;
	int hwl=1;
	int b=0;
	for(auto it=mp.begin();it!=mp.end();++it){
        ans=min(ans,it->second);
        int ds=it->first;
        int oth=qan[ds].size();
        int r=N-hwl-oth;
        if(r>hx||hwl>hx){

        }
        else if(oth>hx){
            b=hx;
            if(qan[ds].size()>hx){
                for(int j=1;b>0;j++,b--){
                    if(j>=qan[ds].size())ok=true;
                    int len=dis(qan[ds][j],qan[ds][0]);
                    len=dis(qan[ds][j],y)-len;
                    len/=2;
                    if(len==ds){
                        oth--;
                    }
                }
                if(oth>hx)ok=true;
            }
            else{
                ok=true;
            }
        }
	}
	return ans*(ok==true ? 1:-1);
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:62:29: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         int oth=qan[ds].size();
                 ~~~~~~~~~~~~^~
towns.cpp:69:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(qan[ds].size()>hx){
                ~~~~~~~~~~~~~~^~~
towns.cpp:71:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(j>=qan[ds].size())ok=true;
                        ~^~~~~~~~~~~~~~~~
towns.cpp:54:6: warning: unused variable 'hwx' [-Wunused-variable]
  int hwx=1;
      ^~~
towns.cpp:8:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1784 KB Output is correct
2 Correct 21 ms 2424 KB Output is correct
3 Correct 2 ms 2424 KB Output is correct
4 Correct 22 ms 2424 KB Output is correct
5 Correct 22 ms 2424 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2804 KB Output is correct
2 Correct 18 ms 2804 KB Output is correct
3 Correct 37 ms 2804 KB Output is correct
4 Correct 22 ms 2804 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 2804 KB Output isn't correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 2844 KB Output isn't correct
2 Halted 0 ms 0 KB -