Submission #846380

#	Time	Username	Problem	Language	Result	Execution time	Memory
846380		vjudge1	KOVANICE (COI15_kovanice)	C++17	0 / 100	897 ms	57032 KiB

kovanice

#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 (stderr)

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
• Subtask 2: 0 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40