| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 163248 |
2019-11-12T01:14:20 Z |
JACK |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
1022 ms |
131240 KB |
#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
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);
~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
24312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
208 ms |
33632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
106 ms |
46372 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
22844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1022 ms |
131240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
993 ms |
130768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
206 ms |
50808 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
204 ms |
51592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
212 ms |
51600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
202 ms |
51544 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
