oj.uz

답안 #846380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846380 2023-09-07T14:12:07 Z vjudge1 KOVANICE (COI15_kovanice) C++17
0 / 100
 897 ms 57032 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl

struct node {
    int val;
    vector<int> a,y,e;
    int deg = 0;
};

vector<node> nodes;
vector<int> res;
queue<int> q;
map<int,int> seen;
int bfs(int x,int n) {
    q.push(x);
    int mxd = -1, mind = 1e9;
    vector<int> visited;
    while (q.size()) {
        auto f = q.front();
        mxd = max(mxd,nodes[f].deg);
        mind = min(mind,nodes[f].deg);
        visited.push_back(f);
        if (seen[f]) {
            q.pop();continue;
        }seen[f]=1;
        for (int i = 0;i<nodes[f].y.size();i++) {
            nodes[nodes[f].y[i]].deg=nodes[f].deg+1;
            q.push(nodes[f].y[i]);
        }
        for (int i = 0;i<nodes[f].a.size();i++) {
            nodes[nodes[f].a[i]].deg=nodes[f].deg-1;
            q.push(nodes[f].a[i]);
        }
        for (int i = 0;i<nodes[f].e.size();i++) {
            nodes[nodes[f].e[i]].deg=nodes[f].deg;
            q.push(nodes[f].e[i]);
        }
    }
    if (mxd-mind != n-1) return 0;
    for (int i = 0;i<visited.size();i++) {
        res[visited[i]] = nodes[visited[i]].deg+1-mind;
    }
    return 0;
}

int32_t main() {
    int n,m,v;cin>>n>>m>>v;
    nodes = vector<node>(m+1);
    res = vi(m+1,-1);
    for (int i = 0;i<m;i++) {
        int a,c;char b;cin>>a>>b>>c;
        if (b=='='){
            nodes[a].e.push_back(c);
            nodes[c].e.push_back(a);
        } else {
            nodes[a].y.push_back(c);
            nodes[c].a.push_back(a);
        }
    }  

    
    for (int i = 0;i<m;i++) {
        if (seen[i+1]) continue;
        bfs(i+1,n);
    }
    for (int i = 1;i<res.size();i++) {
        if (res[i]!=-1) cout<<"K"<<res[i]<<endl;
        else cout<<"K?"<<endl;
    }
    return 0;
}

Compilation message

kovanice.cpp: In function 'int bfs(int, int)':
kovanice.cpp:37:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int i = 0;i<nodes[f].y.size();i++) {
      |                        ~^~~~~~~~~~~~~~~~~~
kovanice.cpp:41:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0;i<nodes[f].a.size();i++) {
      |                        ~^~~~~~~~~~~~~~~~~~
kovanice.cpp:45:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int i = 0;i<nodes[f].e.size();i++) {
      |                        ~^~~~~~~~~~~~~~~~~~
kovanice.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0;i<visited.size();i++) {
      |                    ~^~~~~~~~~~~~~~~
kovanice.cpp: In function 'int32_t main()':
kovanice.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 1;i<res.size();i++) {
      |                    ~^~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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