oj.uz

Submission #683719

# Submission time Handle Problem Language Result Execution time Memory
683719 2023-01-19T08:08:51 Z aSSSd Logičari (COCI21_logicari) C++14
20 / 110
 131 ms 3020 KB 
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r)
{
    return l+rng()%(r-l+1);
}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define forinc(x,a,b) for(int x=a;x<=b;x++)
#define fordec(x,a,b) for(int x=a;x>=b;x--)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ll long long
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define getbit(x,i) ((x>>(i))&1)
#define batbit(x,i) (x|(1ll<<(i)))
#define tatbit(x,i) (x&~(1<<(i)))
#define gg exit(0);
#define int long long
#define ii pair<int,int>
const int N = 1e5 + 100;
int n;
int cnt[22];
ii edge[N];
main()
{
    fasty;
    cin >> n;
    forinc(i,1,n)
    {
        int u,v;
        cin >> u >> v;
        edge[i] = {u,v};
    }
    if(n<=20)
    {
        int res=1e8;
        int lim=(1<<n)-1;
        forinc(mask , 0 , lim)
        {
            memset(cnt,0,sizeof cnt);
            forinc(i,1,n)
            {
                int u = edge[i].fi;
                int v = edge[i].se;
                if(getbit(mask , u-1)) cnt[v]++;
                if(getbit(mask,v-1)) cnt[u]++;
            }
            int ok=1;
            forinc(i,1,n)
            {
                if(cnt[i] != ok)
                {
                    ok=0;
                    break;
                }
            }
            int sl = __builtin_popcount(mask);
            if(ok) res = min(res , sl);
        }
        if(res>=1e8)
        {
            cout << -1;
            return 0;
        }
        cout << res;
        return 0;
    }
    if(n%4 == 0 )
    {
        cout << n/2;
        return 0;
    }
    cout << -1;

}

Compilation message

Main.cpp:31:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   31 | main()
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 15 ms 3012 KB Output is correct
6 Correct 16 ms 2952 KB Output is correct
7 Correct 21 ms 3020 KB Output is correct
8 Correct 21 ms 2992 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 328 KB Output is correct
2 Correct 131 ms 312 KB Output is correct
3 Correct 116 ms 308 KB Output is correct
4 Correct 120 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 60 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 26 ms 212 KB Output is correct
9 Correct 99 ms 212 KB Output is correct
10 Correct 95 ms 212 KB Output is correct
11 Correct 16 ms 212 KB Output is correct
12 Correct 108 ms 308 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 328 KB Output is correct
2 Correct 131 ms 312 KB Output is correct
3 Correct 116 ms 308 KB Output is correct
4 Correct 120 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 60 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 26 ms 212 KB Output is correct
9 Correct 99 ms 212 KB Output is correct
10 Correct 95 ms 212 KB Output is correct
11 Correct 16 ms 212 KB Output is correct
12 Correct 108 ms 308 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 15 ms 3012 KB Output is correct
6 Correct 16 ms 2952 KB Output is correct
7 Correct 21 ms 3020 KB Output is correct
8 Correct 21 ms 2992 KB Output is correct
9 Correct 124 ms 328 KB Output is correct
10 Correct 131 ms 312 KB Output is correct
11 Correct 116 ms 308 KB Output is correct
12 Correct 120 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 60 ms 212 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 26 ms 212 KB Output is correct
17 Correct 99 ms 212 KB Output is correct
18 Correct 95 ms 212 KB Output is correct
19 Correct 16 ms 212 KB Output is correct
20 Correct 108 ms 308 KB Output is correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -