Submission #81018

#	Time	Username	Problem	Language	Result	Execution time	Memory
81018		luckyboy	Usmjeri (COCI17_usmjeri)	C++14	140 / 140	515 ms	145816 KiB

usmjeri

/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 300005
#define maxm 500005
#define pii pair <int,int>
#define Task "Usmjeri"
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n,m,par[maxn][19],h[maxn],lim[maxn],color[maxn];
vector <int> a[maxn];
vector <pair <int,bool> > b[maxn];
void Enter()
{
    read(n);read(m);
    FOR(i,1,n-1)
    {
        int x,y;
        read(x);
        read(y);
        a[x].pb(y);
        a[y].pb(x);
    }
}
void Dfs(int u)
{
    for (int v : a[u])
        if (par[u][0] != v)
        {
            par[v][0] = u;
            h[v] = h[u] + 1;
            FOR(i,1,18) par[v][i] = par[par[v][i-1]][i-1];
            Dfs(v);
        }
}
int Lca(int u,int v)
{
    if (h[u] < h[v]) swap(u,v);
    int dis = h[u] - h[v];
    FOR(i,0,18)
        if ((dis >> i) & 1) u = par[u][i];
    if (u == v) return u;
    FORD(i,18,0)
        if (par[u][i] != par[v][i])
        {
            u = par[u][i];
            v = par[v][i];
        }
    return par[u][0];
}
void Add_edge(int u,int v,bool cl)
{
    b[u].pb(mp(v,cl));
    b[v].pb(mp(u,cl));
}
int Paint_Green(int u)
{
    for (int v : a[u])
        if (v != par[u][0])
        {
            int temp = Paint_Green(v);
            lim[u] = min(lim[u],temp);
            if (temp < h[u]) Add_edge(u,v,0);
        }
    return lim[u];
}
bool Pro(int u,bool cur)
{
    if (color[u] != -1) return color[u] == cur;
    color[u] = cur;
    for (auto v : b[u])
        if (!Pro(v.F,cur ^ v.S)) return 0;
    return 1;
}
int main()
{
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    Enter();
    Dfs(h[1] = 1);
    FOR(i,1,n) lim[i] = h[i];
    while (m--)
    {
        int x,y;
        read(x);read(y);
        int c = Lca(x,y);
        lim[x] = min(lim[x],h[c]);
        lim[y] = min(lim[y],h[c]);
        if (c != x && c != y) Add_edge(x,y,1);
    }
    FOR(i,1,n) color[i] = -1;
    Paint_Green(1);
    int ans = 1;
    FOR(i,2,n)
        if (color[i] == -1)
                ans = (2 * ans * Pro(i,0)) % maxc;
    write(ans);
    return 0;
}

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