Submission #163248

#	Time	Username	Problem	Language	Result	Execution time	Memory
163248		JACK	Usmjeri (COCI17_usmjeri)	C++14	28 / 140	1022 ms	131240 KiB

usmjeri

#include<bits/stdc++.h>
#define ii pair <long long, long long>
#define fi first
#define se second
#define ll long long
#define maxN 100010
using namespace std;
bool ok=true, check=true, chk=true;
ll n, m, dem, ck[300010], base=1e9+7, child[300010], parent[300010], id[5050][5050], d[300010];
ll res, res1, res2, cnt, dd[300010], ddd[5050][5050];
ii pos[300010], chain[300010];
vector <ll> a[300010], w[300010];
void inp ()
{
    //freopen ("usmjeri.inp", "r", stdin);
    //freopen ("usmjeri.out", "w", stdout);
    scanf ("%lld%lld", &n, &m);
    for (int i=1; i<=n-1; i++)
    {
        ll u, v;
        scanf ("%lld%lld", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
        if (abs(u-v)!=1) check=false;
    }
}
ll power (int a, int b)
{
    if (b==0) return 1;
    if (b==1) return a;
    ll c=power(a, b/2);
    if (b%2==0) return ((c%base)*(c%base))%base;
    else return ((c%base)*(c%base)*a)%base;
}
void dfs (int u, int par, int finish)
{
    if (u==finish)
    {
        ok=false;
        return;
    }
    if (ok==true)
    for (int i=0; i<a[u].size(); i++)
    {
        int v=a[u][i];
        if (v!=par)
        {
            child [u]=v;
            parent[v]=u;
            dfs (v, u, finish);
            if (ok==false) return;
        }
    }
}
void dfss (int u, int par)
{
    for (int i=0; i<a[u].size(); i++)
    {
        int v=a[u][i];
        if (v!=par)
        {
            dem++;
            id[u][v]=dem;
            id[v][u]=dem;
            dfss (v, u);
        }
    }
}
void DFS (int u, int par)
{
    if (d[u]==1)
    {
        chk=false;
        printf ("0");
        exit(0);
    }
    d[u]=1;
    if (chk==true)
    for (int i=0; i<w[u].size(); i++)
    {
        int v=w[u][i];
        if (v!=par)
        {
            DFS (v, u);
        }
    }
}
void sub1 ()
{
    for (int i=1; i<=m; i++)
    {
        scanf ("%lld%lld", &pos[i].fi, &pos[i].se);
        if (pos[i].fi>pos[i].se) swap(pos[i].fi, pos[i].se);
    }
    sort (pos+1, pos+m+1);
    for (int i=1; i<=m; i++)
    {
        chain[i].fi=1e18;
        chain[i].se=-1e18;
    }
    dem=1;
    chain[1].fi=min(chain[1].fi, pos[1].fi);
    chain[1].se=max(chain[1].se, pos[1].se);
    for (int i=2; i<=m; i++)
    {
        if (pos[i].fi>=pos[i-1].se) dem++;
        chain[dem].fi=min(chain[dem].fi, pos[i].fi);
        chain[dem].se=max(chain[dem].se, pos[i].se);
    }
    res1=power(2, dem);
    cnt=0;
    for (int i=1; i<=dem; i++)
    {
        ll mu=chain[i].se-chain[i].fi;
        cnt+=mu;
    }
    res2=power(2, n-1-cnt);
    res=(res1*res2)%base;
    printf ("%lld", res);
}
void sub2 ()
{
    dem=0;
    dfss(1, 1);
    for (int i=1; i<=m; i++)
    {
        int u, v;
        scanf ("%lld%lld", &u, &v);
        ok=true;
        dfs (u, u, v);
        u=child[u];
        while (u!=v)
        {
            if (ddd[id[parent[u]][u]][id[u][child[u]]]==0)
            {
                w[id[parent[u]][u]].push_back(id[u][child[u]]);
                w[id[u][child[u]]].push_back(id[parent[u]][u]);
                ddd[id[parent[u]][u]][id[u][child[u]]]=1;
                ddd[id[u][child[u]]][id[parent[u]][u]]=1;
            }
            dd[id[parent[u]][u]]=1;
            dd[id[u][child[u]]]=1;
            u=child[u];
        }
    }
    int cnt=0;
    dem=0;
    chk=true;
    for (int i=1; i<=n-1; i++)
    {
        if (dd[i]==1 and d[i]==0)
        {
            cnt++;
            DFS(i, i);
            if (chk==false) break;
        }
        if (dd[i]==0) dem++;
    }
    res=(power(2, cnt)*power(2, dem))%base;
    if (chk==true) printf ("%lld", res);
}
int main ()
{
    inp ();
    if (check==true) sub1 ();
    else sub2();
    return 0;
}

Compilation message (stderr)

usmjeri.cpp: In function 'void dfs(int, int, int)':
usmjeri.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<a[u].size(); i++)
                   ~^~~~~~~~~~~~
usmjeri.cpp: In function 'void dfss(int, int)':
usmjeri.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<a[u].size(); i++)
                   ~^~~~~~~~~~~~
usmjeri.cpp: In function 'void DFS(int, int)':
usmjeri.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<w[u].size(); i++)
                   ~^~~~~~~~~~~~
usmjeri.cpp: In function 'void sub2()':
usmjeri.cpp:128:34: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
         scanf ("%lld%lld", &u, &v);
                            ~~    ^
usmjeri.cpp:128:34: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'int*' [-Wformat=]
usmjeri.cpp: In function 'void inp()':
usmjeri.cpp:17:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%lld%lld", &n, &m);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~
usmjeri.cpp:21:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%lld%lld", &u, &v);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~
usmjeri.cpp: In function 'void sub1()':
usmjeri.cpp:92:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%lld%lld", &pos[i].fi, &pos[i].se);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
usmjeri.cpp: In function 'void sub2()':
usmjeri.cpp:128:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%lld%lld", &u, &v);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14