| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 706003 |
2023-03-05T18:21:12 Z |
bin9638 |
Towns (IOI15_towns) |
C++17 |
|
25 ms |
1248 KB |
#include <bits/stdc++.h>
#ifndef SKY
#include<towns.h>
#endif
using namespace std;
#define ll long long
#define fs first
#define sc second
#define N 210
#define pb push_back
#define ii pair<ll,ll>
int dem,dis[N][N],c[N][N],S,T,L,R,K;
#ifdef SKY
int getDistance(int i, int j)
{
dem++;
return dis[i][j];
}
#endif // SKY
bool cung_phia(int u,int v,int hub)
{
c[u][v]=c[v][u]=getDistance(u,v);
//cout<<L<<" "<<R<<" "<<K<<" "<<c[S][u]-c[0][u]<<" "<<L-K<<endl;
if(hub==L&&(c[S][u]-c[0][u]>L-K||c[S][v]-c[0][v]>L-K))
return(c[S][u]-c[0][u]>L-K&&c[S][v]-c[0][v]>L-K);
int length_u=(c[S][u]-c[0][u]>=L-K ? L : (c[S][u]+c[0][u]+c[0][S])/2-c[0][u]),
length_v=(c[S][v]-c[0][v]>=L-K ? L : (c[S][v]+c[0][v]+c[0][S])/2-c[0][v]);
if(length_u!=length_v)
return(hub<min(length_u,length_v)||hub>max(length_u,length_v));
if(length_u!=hub)
return 1;
return(!(hub*2+c[u][v]==c[S][u]+c[S][v]));
}
bool check(int hub,int n)
{
// cout<<cung_phia(10,0,hub)<<endl;
stack<int>bucket,lis;
lis.push(0);
for(int i=1;i<n;i++)
if(cung_phia(lis.top(),i,hub))
{//cung nhom
// cout<<i<<" "<<lis.top()<<endl;
bucket.push(i);
}else
{
lis.push(i);
if(!bucket.empty())
{
lis.push(bucket.top());
bucket.pop();
}
}
//cout<<dem<<endl;
//cout<<lis.size()<<endl;
int val=lis.top();
while(!lis.empty())
{
//cout<<"cc\n";
if(bucket.empty())
return 0;
if(cung_phia(val,lis.top(),hub))
{
// cout<<lis.size()<<endl;
for(int i=1;i<=2;i++)
if(!lis.empty())
lis.pop();
}else
{
//cout<<lis.size()<<endl;
lis.pop();
bucket.pop();
}
// cout<<lis.size()<<endl;
if(bucket.empty())
return 0;
}
return 1;
}
int hubDistance(int n, int sub)
{
memset(c,0,sizeof(c));
dem=0;
for(int i=1;i<n;i++)
c[0][i]=c[i][0]=getDistance(0,i);
S=1;
for(int i=1;i<n;i++)
if(c[0][i]>c[0][S])
S=i;
// da tinh 0
for(int i=1;i<n;i++)
if(i!=S)
c[S][i]=c[i][S]=getDistance(S,i);
T=0;
for(int i=0;i<n;i++)
if(c[S][i]>c[S][T])
T=i;
L=(c[S][T]+c[0][S]+c[0][T])/2-c[0][T],
R=(c[S][T]+c[0][S]+c[0][T])/2-c[0][S],
K=(c[S][T]+c[0][S]+c[0][T])/2-c[S][T];
int res=max(L,R);
//cout<<S<<" "<<T<<" "<<L<<" "<<R<<" "<<K<<endl;
vector<int>hub={L};
for(int i=1;i<n;i++)
if(!(c[S][i]-c[0][i]>=L-K))
{
int length=(c[S][i]+c[0][i]+c[0][S])/2-c[0][i];
if(res>max(length,c[S][T]-length))
hub.clear();
res=min(res,max(length,c[S][T]-length));
if(max(length,c[S][T]-length)==res)
hub.pb(length);
}
sort(hub.begin(),hub.end());
hub.erase(unique(hub.begin(),hub.end()),hub.end());
//for(auto cc:hub)cout<<cc<<" ";cout<<endl;
// for(int i=0;i<n;i++)
// for(int j=0;j<i;j++)
// if(cung_phia(i,j,hub[0]))cout<<i<<" "<<j<<endl;
// cout<<dem<<endl;
/*for(int i=0;i<n;i++)
{
if(c[S][i]-c[0][i]>=L-K)
{
cout<<i<<endl;
continue;
}
int length=(c[S][i]+c[0][i]+c[0][S])/2-c[0][i];
if(length>hub[0])
cout<<i<<endl;
}*/
if(hub.size()==1)
return res*(check(hub[0],n)==1 ? -1 : 1);
int cnt=0;
for(int i=1;i<n;i++)
if(!(c[S][i]-c[0][i]>=L-K))
{
int length=(c[S][i]+c[0][i]+c[0][S])/2-c[0][i];
if(length<hub[1])
cnt++;
}
if(cnt*2<=n)
return res*(check(hub[1],n)==1 ? -1 : 1);
return res*(check(hub[0],n)==1 ? -1 : 1);
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
int q,sub;
cin>>sub>>q;
while(q--)
{
int n;
cin>>n;
//cout<<n<<endl;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>dis[i][j];
cout<<hubDistance(n, sub)<<endl;
// cout<<dem<<endl;
}
return 0;
}
#endif // SKY
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:103:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
103 | for(int i=0;i<n;i++)
| ^~~
towns.cpp:106:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
106 | L=(c[S][T]+c[0][S]+c[0][T])/2-c[0][T],
| ^
towns.cpp:88:28: warning: unused parameter 'sub' [-Wunused-parameter]
88 | int hubDistance(int n, int sub)
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1020 KB |
Output is correct |
| 2 |
Correct |
11 ms |
900 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
25 ms |
1008 KB |
Output is correct |
| 5 |
Correct |
18 ms |
1048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
14 ms |
980 KB |
Output is correct |
| 3 |
Correct |
15 ms |
1028 KB |
Output is correct |
| 4 |
Correct |
25 ms |
980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
852 KB |
Output is correct |
| 2 |
Correct |
14 ms |
964 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
20 ms |
964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
1248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
948 KB |
Output is correct |
| 2 |
Correct |
25 ms |
944 KB |
Output is correct |
| 3 |
Correct |
15 ms |
1032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
960 KB |
Output is correct |
| 2 |
Correct |
18 ms |
1032 KB |
Output is correct |
| 3 |
Correct |
20 ms |
1032 KB |
Output is correct |
