oj.uz

Submission #82596

# Submission time Handle Problem Language Result Execution time Memory
82596 2018-10-31T14:56:53 Z Genezio Usmjeri (COCI17_usmjeri) C++14
0 / 140
 171 ms 3016 KB 
#include<bits/stdc++.h>

using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define ll long long

const int N = 500010;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9+7;

 pii v[N];

 ll exp(int x) {
 	if(x==1) return 2;
 	if(x%2) return (2*exp(x-1))%mod;
 	ll aux = exp(x/2);
 	return (aux*aux)%mod;
 }


int main() {
	ios::sync_with_stdio(false);
 	cin.tie(0);
    int n,m;
    cin>>n>>m;
    int a,b;
    for(int i=1;i<n;i++) {
        cin>>a>>b;
    }
    for(int i=0;i<m;i++) {
    	cin>>v[i].F>>v[i].S;
    	if(v[i].F>v[i].S) swap(v[i].F,v[i].S);
    }
    sort(v,v+m);
    int p=0;
    int ng=0;
   	a=v[0].F;
   	b=v[0].S;
    for(int i=1;i<m;i++) {
    	if(v[i].F<=b) {
    		b=v[i].S;
    	} else {
    		p+=(b-a);
    		a=v[i].F;
    		b=v[i].S;
    		ng++;
    	}
    }
    p+=(b-a);
    ng++;
    cout<<exp(n-1-p+ng)%mod<<"\n";
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 1884 KB Output isn't correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 2684 KB Output isn't correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 2888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 2888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 2888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 3016 KB Output isn't correct
2 Halted 0 ms 0 KB -