Code: Select all
Accepted... :)
Moderator: Board moderators
Code: Select all
Accepted... :)
The method you use to read input:Mukit Chowdhury wrote:Got TLE... Help please...
Code: Select all
while(~scanf("%d",&n))
Code: Select all
while(scanf("%d",&n) == 1)
Code: Select all
15 5 19 16 15 5 1 2 8 6 11 2 1 6 11 18
16
13 1
13 14
1 11
6 12
8 1
9 3
15 2
13 6
13 15
7 14
15 14
8 13
6 14
15 1
9 14
14 12
15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Code: Select all
Set #1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
I tried withlbv wrote: The method you use to read input:is interesting, but it gets the program stuck in an infinite loop if the input happens to contain strange characters at the end of the file, which apparently is the case for this problem. You could try instead:Code: Select all
while(~scanf("%d",&n))
Code: Select all
while(scanf("%d",&n) == 1)
Code: Select all
while(scanf("%d",&n) != EOF)
Anything that doesn't conform to what scanf understands as an integer would cause the problem.Mukit Chowdhury wrote: I tried with (..)
but it also failed... and gave me same verdict... :/
what kind of strange character can appear in end of file ??? would you please give me a example ??? it will really help....
Code: Select all
5 6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
Code: Select all
5 6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
A
Code: Select all
The first line of each test case contains n (the number of junctions, 0 <= n <= 200)
Code: Select all
while(scanf("%d",&n)==1)
Code: Select all
while(~scanf("%d",&n))
Code: Select all
while(scanf("%d",&n)!=EOF)
Code: Select all
Deleted...
Though it sounds strange according to problem statement... anyway... Thanks for ensuring me about non digit character of the last input...brianfry713 wrote:Yes it appears that the judge's input does not conform to the problem statement. There is a non-digit char after the last input.
Code: Select all
#include <bits/stdc++.h>
using namespace std;
const int INF=100000000;
int cost[505],weight[505][505],dist[505],inCycle[505];
vector<int>adj[505];
int main(){
int n,r,a,b,t=0;
while(scanf("%d",&n)==1){
t++;
for(int i=0;i<n;i++){
scanf("%d",&cost[i]);
adj[i].clear();
}
scanf("%d",&r);
for(int i=0;i<r;i++){
scanf("%d%d",&a,&b);
a--; b--;
adj[a].push_back(b);
weight[a][b]=(cost[b]-cost[a])*(cost[b]-cost[a])*(cost[b]-cost[a]);
}
for(int i=0;i<n;i++)dist[i]=INF;
dist[0]=0;
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<(int)adj[i].size();j++){
int u=i,v=adj[i][j];
if(dist[u]==dist[v] && dist[u]==INF)continue;
dist[v]=min(dist[v],dist[u]+weight[u][v]);
}
memset(inCycle,0,sizeof inCycle);
for(int i=0;i<n;i++)
for(int j=0;j<(int)adj[i].size();j++){
int u=i,v=adj[i][j];
if(dist[u]+weight[u][v]<dist[v]){
inCycle[v]=1;
}
}
int q;
printf("Set #%d\n",t);
scanf("%d",&q);
for(int i=0;i<q;i++){
scanf("%d",&a);
a--;
if(dist[a]<3 || inCycle[a] || dist[a]==INF)printf("?\n");
else printf("%d\n",dist[a]);
}
}
return 0;
}
Code: Select all
#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define sz(x) x.size()
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case(z,x) cout<<"Case "<<i<<": "<<x<<endl
#define case(z) cout<<"Case "<<z<<": "
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define MAX 300
#define inf 10000000
/*---------------------------Graph Moves-----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*------------------------------------------------------------------*/
using namespace std;
int dis[MAX],parent[MAX];
vector<int>gu,gv,cost;
int node,edge;
map <int, int> mp;
bool bellman_ford()
{
loop0(i,MAX)
{
dis[i]=inf;
}
dis[1]=0;
loop1(i,node)
{
bool change=0;
loop0(j,edge)
{
int u=gu[j];
int v=gv[j];
if(dis[u]+cost[j]<dis[v])
{
change=1;
dis[v]=dis[u]+cost[j];
}
}
if(change==0) return 1;
}
}
int main()
{
CIN;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int n_cost,t;
t=0;
while(cin>>node)
{
//cout<<endl;
t++;
loop1(i,node)
{
cin>>n_cost;
mp[i]=n_cost;
}
cin>>edge;
loop0(i,edge)
{
int from,to,w;
cin>>from>>to;
gu.pb(from);
gv.pb(to);
w=mp[to]-mp[from];
cost.pb(w*w*w);
}
int q,n;
cin>>q;
cout<<"Set #"<<t<<endl;
int a=bellman_ford();
loop0(i,q)
{
cin>>n;
if(dis[n]<3 || dis[n]>100000)
{
cout<<"?"<<endl;
}
else
{
cout<<dis[n]<<endl;
}
}
gu.clear();
gv.clear();
cost.clear();
mp.clear();
}
return 0;
}