oj.uz

Submission #1120496

# Submission time Handle Problem Language Result Execution time Memory
1120496 2024-11-28T07:56:56 Z vjudge1 KOVANICE (COI15_kovanice) C++17
50 / 100
 578 ms 32136 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld double


const int INF = 1e18;
const int mod = 12345;
const int sz = 3e5 + 5;

vector < bool > vis(sz , false);
vector < vector < int > > adj(sz);
vector < int > ans(sz + 1 , -1);

void dfs(int v)
{
    vis[v] = 1;
    for(int u : adj[v])
    {
        if(!vis[u]){
            ans[u] = ans[v];
            dfs(u);
        }
    }
}

signed main()
{
   ios_base::sync_with_stdio(0);cin.tie(0);
   int n , m , v;
   cin >> n >> m >> v;
   vector < string > q1;
   vector < string > q2;
   for(int i = 1;i <= v;i++)
   {
       string s;
       cin >> s;
       bool f = 0;
       for(char c : s)
       {
           if(c == '=')
           {
               f = 1;
               q2.push_back(s);
               continue;
           }
       }
       if(!f) q1.push_back(s);
   }
   for(int i = 0;i < q1.size();i++)
   {
       string s = q1[i];
       string r1 = "";
       string r2 = "";
       int in = -1;
       char q;
       for(int j = 0;j < s.size();j++)
       {
           if(s[j] == '>' or s[j] == '<')
           {
               in = j;
               q = s[j];
               break;
           }
           r1 += s[j];
       }
       for(int j = in + 1;j < s.size();j++) r2 += s[j];
       int x1 = stoi(r1);
       int x2 = stoi(r2);
       if(q == '<')
       {
           ans[x1] = 1;
           ans[x2] = 2;
       }
       else
       {
           ans[x1] = 2;
           ans[x2] = 1;
       }
   }
   vector < pair < int , int > > b;
   for(int i = 0;i < q2.size();i++)
   {
       string s = q2[i];
       string r1 = "";
       string r2 = "";
       int in = -1;
       for(int j = 0;j < s.size();j++)
       {
           if(s[j] == '=')
           {
               in = j;
               break;
           }
           r1 += s[j];
       }
       for(int j = in + 1;j < s.size();j++) r2 += s[j];
       int x1 = stoi(r1);
       int x2 = stoi(r2);
       adj[x1].push_back(x2);
       adj[x2].push_back(x1);
       b.push_back({x1,x2});
   }
   vector < int > v1;
   for(int i = 1;i <= m;i++)
   {
       if(ans[i] != -1) v1.push_back(i);
       if(ans[i] != -1) vis[i] = 1;
   }
   for(int i : v1)
   {
       dfs(i);
   }
   for(int i = 1;i <= m;i++)
   {
       if(ans[i] == -1)
       {
           cout << "?" << endl;
       }
       else
       {
           cout << "K" << ans[i] << endl;
       }
   }
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:51:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for(int i = 0;i < q1.size();i++)
      |                  ~~^~~~~~~~~~~
kovanice.cpp:58:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |        for(int j = 0;j < s.size();j++)
      |                      ~~^~~~~~~~~~
kovanice.cpp:68:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |        for(int j = in + 1;j < s.size();j++) r2 += s[j];
      |                           ~~^~~~~~~~~~
kovanice.cpp:83:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for(int i = 0;i < q2.size();i++)
      |                  ~~^~~~~~~~~~~
kovanice.cpp:89:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |        for(int j = 0;j < s.size();j++)
      |                      ~~^~~~~~~~~~
kovanice.cpp:98:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |        for(int j = in + 1;j < s.size();j++) r2 += s[j];
      |                           ~~^~~~~~~~~~
kovanice.cpp:71:8: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |        if(q == '<')
      |        ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9808 KB Output is correct
2 Correct 10 ms 10048 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 18352 KB Output is correct
2 Correct 316 ms 19112 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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