oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

alliance Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

alliance.txt

Problem 3: Bovine Alliance [Mark Gordon, 2011]

Bessie and her bovine pals from nearby farms have finally decided that they
are going to start connecting their farms together by trails in an effort
to form an alliance against the farmers.  The cows in each of the N (1 <= N
<= 100,000) farms were initially instructed to build a trail to exactly one
other farm, for a total of N trails.  However months into the project only
M (1 <= M < N) of these trails had actually been built.

Arguments between the farms over which farms already built a trail now
threaten to split apart the cow alliance.  To ease tension, Bessie wishes
to calculate how many ways the M trails that exist so far could have been
built.  For example, if there is a trail connecting farms 3 and 4, then one
possibility is that farm 3 built the trail, and the other possibility is
that farm 4 built the trail.  Help Bessie by calculating the number of
different assignments of trails to the farms that built them, modulo
1,000,000,007.  Two assignments are considered different if there is at
least one trail built by a different farm in each assignment.

PROBLEM NAME: alliance

INPUT FORMAT:

* Line 1: Two space-separated integers N and M

* Lines 2..1+M: Line i+1 describes the ith trail.  Each line contains
        two space-separated integers u_i and v_i (1 <= u_i, v_i <= N,
        u_i != v_i) describing the pair of farms connected by the
        trail.

SAMPLE INPUT (file alliance.in):

5 4
1 2
3 2
4 5
4 5

INPUT DETAILS:

Note that there can be two trails between the same pair of farms.

OUTPUT FORMAT:

* Line 1: A single line containing the number of assignments of trails
        to farms, taken modulo 1,000,000,007.  If no assignment
        satisfies the above conditions output 0.

SAMPLE OUTPUT (file alliance.out):

6

OUTPUT DETAILS:

There are 6 possible assignments.  Letting {a,b,c,d} mean that farm 1
builds trail a, farm 2 builds trail b, farm 3 builds trail c, and farm 4
builds trail d, the assignments are:
{2, 3, 4, 5}
{2, 3, 5, 4}
{1, 3, 4, 5}
{1, 3, 5, 4}
{1, 2, 4, 5}
{1, 2, 5, 4}

Tags

USACO Gold Jan 2012

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100111s16MBAverage

Judge Compile Command

g++-8 ans.cpp -o alliance -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.