Submission #308027

#	Time	Username	Problem	Language	Result	Execution time	Memory
308027		qiangbao	Dijamant (COI16_dijament)	C++98	100 / 100	1046 ms	10748 KiB

dijament

#include <iostream>
#include <vector>
#include <bitset>
#include <map>

#define pb push_back

using namespace std;

int n;
vector<int> top;
vector<int> father[1001];

int cnt=0;
map<string, int> topos;
bitset<1001> mp[1001];
bitset<1001> cur;
bool decla[1001];

int conflic[1001][1001];
bool vis[1001];

bool ans=true;

void up(int x)
{
    int i;

    if(vis[x])
        return;
    cur.set(x, 1), vis[x]=true;
    for(i=0;i<father[x].size();i++)
        up(father[x][i]);
}

int consis()
{
    int i, j;

    for(i=0;i<=1000;i++)
        vis[i]=false;
    for(i=0;i<top.size();i++)
        up(top[i]);
    for(i=0;i<top.size();i++){
        for(j=i+1;j<top.size();j++){
            int x=top[i], y=top[j];
            if(conflic[x][y]==0){
                if(mp[x].test(y)==1 || mp[y].test(x)==1)
                    conflic[x][y]=conflic[y][x]=-1;
                else{
                    bitset<1001> f=mp[x]&mp[y];
                    if(f.count()>=1)
                        conflic[x][y]=conflic[y][x]=1;
                }
            }
            if(conflic[x][y]==1)
                return 0;
        }
    }

    return 1;
}

void wk()
{
    string in;
    int x;
    ans=true;

    cin >> in;
    if(!topos[in])
        topos[in]=++cnt;
    x=topos[in];
    cin >> in;

    top.clear();
    while(in!=";"){
        cin >> in;
        if(in==";")
            break;
        if(!topos[in])
            topos[in]=++cnt;
        top.pb(topos[in]);
        if(!decla[topos[in]])
            ans=false;
    }

    cur.reset();
    if(decla[x])
        ans=false;
    if(ans && !consis())
        ans=false;
    if(ans)
        decla[x]=true, mp[x]=cur, father[x]=top;

    if(ans)
        cout << "ok" << endl;
    else
        cout << "greska" << endl;
}

int main()
{
    ios_base:: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int i;

    cin >> n;
    for(i=1;i<=n;i++)
        wk();

    return 0;
}

Compilation message (stderr)

dijament.cpp: In function 'void up(int)':
dijament.cpp:32:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(i=0;i<father[x].size();i++)
      |             ~^~~~~~~~~~~~~~~~~
dijament.cpp: In function 'int consis()':
dijament.cpp:42:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(i=0;i<top.size();i++)
      |             ~^~~~~~~~~~~
dijament.cpp:44:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(i=0;i<top.size();i++){
      |             ~^~~~~~~~~~~
dijament.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(j=i+1;j<top.size();j++){
      |                   ~^~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 29 / 29
• Subtask 4: 44 / 44