oj.uz

답안 #674338

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
674338 2022-12-23T17:46:14 Z Farhan_HY Logičari (COCI21_logicari) C++14
0 / 110
 1 ms 212 KB 
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define T int t;cin >> t;while(t--)
#define int long long
#define F first
#define S second
using namespace std;
const int mod = 1e9 + 7;
const int N = 355;
int n, depth[N], color[N], v1, v2;
vector<int> adj[N], vec;

bool cmp(int &x, int &y) {
    if (depth[x] == depth[y]) return x < y;
    return depth[x] < depth[y];
}

void dfs(int node, int dep) {
    depth[dep] = dep;
    for(auto x: adj[node]) {
        if (depth[x] == 0)
            dfs(x, dep + 1);
    }
}
stack<int> s;

bool solve() {
    while (vec.size()) {
        int dep = depth[vec.back()];
        while (vec.size() && depth[vec.back()] == dep)
            s.push(vec.back()), vec.pop_back();
        while(s.size()) {
            int u = s.top();
            s.pop();
            int cnt[4] = {0, 0, 0, 0};
            for(auto x: adj[u]) {
                if (depth[x] > depth[u]) 
                    cnt[color[x]]++;
            }
            if ((cnt[0] || cnt[2]) && (cnt[1] || cnt[3])) return 0;
            if (cnt[0] > 0) {
                if (cnt[2] == 0) {
                    color[u] = 2;
                    for(auto x: adj[u])
                        if (depth[x] > depth[u] && color[x] == 0) color[x] = 1;
                }
                else if (cnt[2] == 1) {
                    color[u] = 3;
                    for(auto x: adj[u])
                        if (color[x] == 3) color[x] = 3;
                }
                else return 0;
            }
            else if (cnt[2] > 0) {
                if (cnt[2] > 1) return 0;
                else {
                    color[u] = 3;
                    for(auto x: adj[u])
                        if (color[x] == 2) color[x] = 3;
                }
            }
            else if (cnt[3] > 0) {
                if (cnt[3] > 1) return 0;
                color[u] = 1;
            }
        }
    }
    if (color[v1] == 0) {
        if (color[v2] != 3) return 0;
        color[v1] = 1;
    }
    else if (color[v1] == 1) {
        if (color[v2] != 1) return 0;
    }
    else if (color[v1] == 2) {
        if (color[v1] != 2) return 0;
        color[v1] = color[v2] = 3;
    }
    else {
        if (color[v2] != 1) return 0;
    }
    bool ok = 1;
    for(int i = 1; i <= n; i++) ok &= (color[i] % 2);
    return ok;
}

main() {
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) vec.push_back(i);
    cin >> v1 >> v2;
    dfs(1, 1);
    sort(begin(vec), end(vec), cmp);
    if (solve() == 0) cout << -1;
    else {
        int ans = 0;
        for(int i = 1; i <= n; i++) ans += color[i] == 3;
        cout << ans;
    }
}

Compilation message

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -