oj.uz

Submission #1120534

# Submission time Handle Problem Language Result Execution time Memory
1120534 2024-11-28T08:06:43 Z vjudge1 KOVANICE (COI15_kovanice) C++17
50 / 100
 340 ms 45216 KB 
#include <bits/stdc++.h>
using namespace std;
const int sz = 3e5 + 5;
vector<int> az[sz],cox[sz],ber[sz];
vector<int> ans(sz,-1);
vector<bool> vis(sz,0);

void dfs(int a,int b){
    vis[a] = 1;
    ans[a] = b;
    for(auto &i : az[a]){
        if(!vis[i]){
            dfs(i,1);
        }
    }
    for(auto &i : ber[a]){
        if(!vis[i]){
            dfs(i,b);
        }
    }
    
    for(auto &i : cox[a]){
        if(!vis[i]){
            dfs(i,2);
        }
    }
}

signed main(){
    int n,m,k;
    cin >>  n>> m >> k;
    vector<int> iki,bir;
    string s;
    while(k--){
        cin >> s;
        int a=0,b=0;
        char c='.';
        for(int i=0;i<s.size();++i){
            if(s[i] >= '0' && s[i] <= '9'){
                if(c == '.')a = a * 10 + (s[i] - '0');
                else b = b * 10 + (s[i] - '0');
            }else{
                c = s[i];
            }
        }
        if(c == '='){
            ber[a].push_back(b);
            ber[b].push_back(a);
        }else if(c == '<'){
            iki.push_back(b);
            bir.push_back(a);
            cox[a].push_back(b);
            az[b].push_back(a);
        }else{
            iki.push_back(a);
            bir.push_back(b);
            cox[b].push_back(a);
            az[a].push_back(b);
        }
    }
    for(int _=0;_<5;++_){
        for(auto &temp : cox){
        for(auto &i : temp){
            if(!vis[i])dfs(i,2);
        }
        }
    }
    for(int i=1;i<=m;++i){
        if(ans[i] == -1){
            cout << "?";
        }else{
            cout << "K" << ans[i];
        }
        cout << '\n';
    }
    
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int i=0;i<s.size();++i){
      |                     ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 22864 KB Output is correct
2 Correct 24 ms 22704 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 28480 KB Output is correct
2 Correct 128 ms 29796 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 25184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 340 ms 45216 KB Output isn't correct
2 Halted 0 ms 0 KB -