f.nasim's blog

round 22 problem C
By f.nasim, 14 years ago, In English
What's the problem in the following code? It gets wrong answer on test case 3.

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
    int n,m,v,i;

    scanf("%d %d %d",&n,&m,&v);

    if(m<n-1)
    {
        printf("-1");
        return 0;
    }

    if((m-n+1)>n-3)
    {
        printf("-1");
        return 0;
    }

    for(i=1;i<n;i++)
        printf("%d %d\n",i,i+1);

    int count=0;

    for(i=1;count<m-n+1;i++)
    {
        if(i!=v-1 && i!=v && i!=v+1)
        {
            //printf("%d %d\n",i,v);
            printf("%d %d\n",min(i,v),max(i,v));
            count++;
        }
    }

    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
    if((m-n+1)>n-3)
    {
        printf("-1");
        return 0;
    }

This part is incorrect.
M can be much larger.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    But how? Can you explain.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Basically graph with most edges is full graph on n - 1 vertices en edge from vertex v to remaining vertex
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Like egor says... You take n-1 vertices (including v) and make a complete graph out of them. That's (n-1)(n-2)/2 edges.

      Then, you add one more edge from v to the vertex you left out of your complete graph.

      So in total, (n-1)(n-2)/2 + 1 edges is the most you may be able to use.
      → Reply