Submission #82596

#	Time	Username	Problem	Language	Result	Execution time	Memory
82596		Genezio	Usmjeri (COCI17_usmjeri)	C++14	0 / 140	171 ms	3016 KiB

usmjeri

#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
• Subtask 2: 0 / 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