oj.uz

Submission #723955

# Submission time Handle Problem Language Result Execution time Memory
723955 2023-04-14T14:10:07 Z bane Dijamant (COI16_dijament) C++17
100 / 100
 182 ms 4628 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#define pb push_back
#define fr first
#define sc second
#define pq priority_queue
#define all(x) begin(x), end(x)
#define mp make_pair

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = (ll)1e18;
const ll MOD = (ll)1e9 + 7;
const int MAXN = 2000;
void setPrec() { cout << fixed << setprecision(15); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
    unsyncIO(); setPrec();
    if ((int)s.size()) setIn(s+".in"), setOut(s+".out");
}
int par[MAXN];
void solve(){
    int N; cin >> N;
    map<string,int>vis;
    vector<int>a[N + 1];
    for (int i = 1; i <= N; i++){
        string s;
        cin >> s;
        char c;
        cin >> c;
        vector<int> v;
        bool bad = 0;
        while(1){
            string t;
            cin >> t;
            if(t == ";")break;
            if(vis[t] == 0)bad = 1;
            v.push_back(vis[t]);
        }
        if (vis[s])bad = 1;
       // vis[k] = i;
        if (bad){
            cout<<"greska"<<'\n';
            continue;
        }
        for (int j = 0; j<=N; j++)par[j] = 0;
        function<void(int)>dfs = [&](int v){
            for(auto u:a[v]){
                    if(bad)return;
                    if(par[u]){
                        if(par[u] != v)
                            bad = 1;
                    }
                    else{
                        par[u] = v;
                        dfs(u);
                    }
                }
        };
        for (int p : v)dfs(p);
        if (!bad){
            vis[s] = i;
            cout<<"ok"<<'\n';
            for (auto p : v){
                if (par[p] == 0){
                    //koren
                    a[i].pb(p);
                }
            }
        }else{
            cout<<"greska"<<'\n';
        }
    }
}
int main(){
    setIO();
    solve();
    return 0;
}

Compilation message

dijament.cpp: In function 'void setIn(std::string)':
dijament.cpp:37:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
dijament.cpp: In function 'void setOut(std::string)':
dijament.cpp:38:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 1 ms 252 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 324 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 328 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 4084 KB Output is correct
2 Correct 182 ms 4628 KB Output is correct
3 Correct 172 ms 4508 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 8 ms 596 KB Output is correct
8 Correct 16 ms 716 KB Output is correct
9 Correct 16 ms 724 KB Output is correct
10 Correct 5 ms 468 KB Output is correct
11 Correct 5 ms 464 KB Output is correct
12 Correct 143 ms 3760 KB Output is correct