oj.uz

Submission #540338

# Submission time Handle Problem Language Result Execution time Memory
540338 2022-03-20T05:01:01 Z BadPenalty Logičari (COCI21_logicari) C++14
10 / 110
 111 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
const int N = 1000,mod = 1e9+7;

vector<int>adj[N];
bool blue[N];

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;

    for(int i = 0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;

        adj[a].pb(b);
        adj[b].pb(a);
    }

    int ans = 1e9;

    for(int mask = 0;mask< (1<<n) ;mask++)
    {
        for(int i = 1;i<=n;i++)blue[i] = 0;
        int cur = 0;
        bool tr = 1;
        for(int i = 0;i<n;i++)
        {
            if(mask&(1<<i))
                blue[i+1] = 1,cur++;
        }
        for(int i = 1;i<=n;i++)
        {
            int cnt = 0;
            for(auto u:adj[i])
                cnt+=blue[u];
            if(cnt!=1)
                tr = 0;
        }
        if(tr)
            ans = min(ans,cur);
    }
    if(ans==1e9)
        cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}
/*

*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 212 KB Output is correct
2 Correct 111 ms 212 KB Output is correct
3 Correct 97 ms 340 KB Output is correct
4 Correct 96 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 48 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 23 ms 348 KB Output is correct
9 Correct 98 ms 320 KB Output is correct
10 Correct 96 ms 340 KB Output is correct
11 Correct 12 ms 212 KB Output is correct
12 Correct 98 ms 340 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 212 KB Output is correct
2 Correct 111 ms 212 KB Output is correct
3 Correct 97 ms 340 KB Output is correct
4 Correct 96 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 48 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 23 ms 348 KB Output is correct
9 Correct 98 ms 320 KB Output is correct
10 Correct 96 ms 340 KB Output is correct
11 Correct 12 ms 212 KB Output is correct
12 Correct 98 ms 340 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 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -