# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
211970 | 2020-03-21T20:57:18 Z | tleontest1 | Geppetto (COCI15_geppetto) | C++14 | 20 ms | 20352 KB |
#pragma GCC optimize ("O3") #pragma GCC target ("sse4") #include <bits/stdc++.h> using namespace std; typedef long long lo; typedef pair< lo,lo > PII; #define fi first #define se second #define mp make_pair #define pb push_back #define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define FOR for(int i=1;i<=n;i++) #define mid ((start+end)/2) #define ort ((bas+son)/2) const lo MAX = -1000000000000000000; const lo MIN = 1000000000000000000; const lo inf = 1000000000; const lo KOK = 100000; const lo LOG = 30; const lo li = 500005; const lo mod = 1000000007; int n,m,b[li],a[li],k,flag,t,dp[(1<<21)+1]; int cev; string s; vector<int> v[li]; inline int f(int sira,int mask){ int cevv=0; int no=0; if(sira>=n){ //~ cout<<mask<<endl; return 1; } if(~dp[mask])return dp[mask]; for(int i=0;i<(int)v[sira].size();i++){ //~ cout<<v[sira][i]<<" : : "<<sira<<endl; if((mask&(1<<v[sira][i]))){no=1;break;} } if(no==0){ cevv+=f(sira+1,(mask|(1<<sira))); } cevv+=f(sira+1,mask); return dp[mask]=cevv; } int main(void){ memset(dp,-1,sizeof(dp)); scanf("%d %d",&n,&m); for(int i=1;i<=m;i++){ int x,y; scanf("%d %d",&x,&y); x--; y--; v[x].pb(y); v[y].pb(x); } printf("%d\n",f(0,0)); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 20224 KB | Output is correct |
2 | Correct | 16 ms | 20224 KB | Output is correct |
3 | Correct | 16 ms | 20352 KB | Output is correct |
4 | Correct | 16 ms | 20224 KB | Output is correct |
5 | Correct | 16 ms | 20224 KB | Output is correct |
6 | Correct | 16 ms | 20352 KB | Output is correct |
7 | Correct | 16 ms | 20224 KB | Output is correct |
8 | Correct | 16 ms | 20352 KB | Output is correct |
9 | Correct | 17 ms | 20224 KB | Output is correct |
10 | Correct | 20 ms | 20224 KB | Output is correct |