oj.uz

Submission #902539

# Submission time Handle Problem Language Result Execution time Memory
902539 2024-01-10T15:34:12 Z nightfal Toy Train (IOI17_train) C++14
11 / 100
 2000 ms 262144 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <cassert>
#include <algorithm>


using namespace std;

void printAdjMatrix(vector<vector<int>>& adjM) {
    int n = adjM.size();
    for(int i=0; i<n; i++) {
        printf("%d:",i);
        for(int elem: adjM[i])
            printf(" %d",elem);
        printf("\n");
    }
}
void printAdjList(vector<vector<int>>& adjL) {
    int n = adjL.size();
    for(int i=0; i<n; i++) {
        printf("%d:",i);
        for(int elem: adjL[i])
            printf(" %d", elem);
        printf("\n");
    }
}
void printDegree(vector<int>& Deg) {
    int n = Deg.size();
    for(int i=0; i<n; i++) printf("Deg[%d]=%d ",i,Deg[i]);
    printf("\n");
}

bool isSubtask1(vector<int>& u, vector<int>& v) {
    int m = u.size();
    for(int i=0; i<m; i++)
        if (v[i]!=u[i] && v[i]!=u[i]+1) return false;
    return true;
}
bool isSubtask2(const int n) {return n <= 15;}
bool isSubtask3(const vector<int>& a) {
    for(int i=0; i<a.size(); i++)
        if(a[i]==0) return false;
    return true;
}
bool isSubtask4(const vector<int>& a) {
    for(int i=0; i<a.size(); i++)
        if(a[i]) return false;
    return true;
}

bool dfs(int now, int dest, vector<int>& a, vector<int>& r, vector<vector<int>>& adjL, vector<int>& dis, vector<int>& ans) {
    // printf("now:%d, dest:%d, dis[%d]=%d, r[%d]=%d, ans[%d]=%d\n",now,dest,now,(int) dis[now],now,r[now],now,ans[now]);
    if (now==dest) return true;
    if (dis[now]) return false;
    else dis[now] = 1;
    if (a[now]) {
        for(int i=0; i<adjL[now].size(); i++)
            if(dfs(adjL[now][i],dest,a,r,adjL,dis,ans)) {ans[now]=1; break;}
    }
    else {
        int i;
        for(i=0; i<adjL[now].size(); i++)
            if(!dfs(adjL[now][i],dest,a,r,adjL,dis,ans)) break;
        if (i==adjL[now].size()) ans[now] = 1;
    }
    if (ans[now]) printf("win %d \n",now);
    return ans[now];
}

void checkNeighbor(int now, vector<int>& a, vector<vector<int>>& adjL, vector<int>& ans) {
    if (a[now]) {
        for(int i=0; i<adjL[now].size(); i++)
            if(ans[adjL[now][i]]) ans[now]=1;
    }
    else {
        int i;
        for(i=0; i<adjL[now].size(); i++)
            if(!ans[adjL[now][i]]) break;
        if (i==adjL[now].size()) ans[now] = 1;
    }
}
void dfs3(const int now, const int dest, const vector<vector<int>>& adjL, vector<int>& dis, vector<int>& ans) {
    // printf("now:%d dest:%d\n",now,dest);
    if (dis[now]) return;
    dis[now] = 1;
    if (now==dest) {ans[dest] = 1; /* printf("ans[%d]=%d\n",dest,ans[dest]);*/ return;}
    for(int i=0; i<adjL[now].size(); i++) 
        dfs3(adjL[now][i],dest,adjL,dis,ans);
    return;
}
// bool dfs3(const int now, const int dest, const vector<vector<int>>& adjL, vector<int>& dis, vector<int>& ans) {
//     // printf("now:%d dest:%d\n",now,dest);
//     if (dis[now]) return false;
//     dis[now] = 1;
//     if (now==dest) return true;
//     for(int i=0; i<adjL[now].size(); i++) 
//         if(dfs3(adjL[now][i],dest,adjL,dis,ans)) return true; // {ans[now]=1; return true;}
//     return false;
// }
// bool dfs4(const int now, const int dest, const vector<vector<int>>& adjL, vector<int>& dis, vector<int>& fin, vector<int>& ans) {
//     // printf("now:%d dest:%d\n",now,dest);
//     if (fin[now]) return ans[now];
//     if (now==dest) return true;
//     if (dis[now]) return false;
//     dis[now] = 1;
//     for(int i=0; i<adjL[now].size(); i++) 
//         if(!dfs4(adjL[now][i],dest,adjL,dis,fin,ans)) {fin[now]=1; ans[now]=0;/* printf("ans[%d]=%d\n",now,ans[now]);*/ return false;}
//     fin[now]=1; ans[now]=1; return true;
// }
vector<int> fulltask(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
    int n=a.size(), m=u.size();
    vector<vector<int>> adjL(n+1), adjLRev(n+1);
    for(int i=0; i<m; i++) {adjL[u[i]].push_back(v[i]); adjLRev[v[i]].push_back(u[i]);}

    vector<int> ans(n), cnt(n), ans2(n);
    queue<int> q;

    for(int i=0; i<n; i++) if(r[i]) {ans[i]=1;} // cout << "push: " << i << endl;}

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) if (ans[j]==1) q.push(j);
        cnt.assign(n,0); ans2.assign(n,0);
        while(!q.empty()) {
            int node = q.front(); q.pop(); 
            for(int elem: adjLRev[node]) {
                cnt[elem]++;
                if (a[elem] || cnt[elem]==adjL[elem].size()) {
                    ans2[elem]=1; 
                    if(!ans[elem]) q.push(elem);
                    // printf("ans2[%d]=1 ", elem); cout << "push: " << elem << endl;
                }
            }
        }
        // for(int j=0; j<n; j++) printf("ans [%d]=%d ",j,ans[j]); printf("\n"); 
        // for(int j=0; j<n; j++) printf("ans2[%d]=%d ",j,ans2[j]); printf("\n\n"); 
        bool update=false;
        for(int j=0; j<n; j++) if(ans[j]&&!ans2[j]) {ans[j] = 0; update=true;}
        // printf(update? "yes\n":"no\n");
        // for(int j=0; j<n; j++) printf("ans [%d]=%d ",j,ans[j]); printf("\n"); 

        if (!update) return ans2;
    }
}
vector<int> subtask4(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
    // printf("subtask4\n");
    int n=a.size(), m=u.size();
    vector<vector<int>> adjL(n+1), adjLRev(n+1);
    for(int i=0; i<m; i++) {adjL[u[i]].push_back(v[i]); adjLRev[v[i]].push_back(u[i]);}

    vector<int> ans(n), cnt(n), ans2(n);
    queue<int> q;

    for(int i=0; i<n; i++) if(r[i]) {ans[i]=1;} // cout << "push: " << i << endl;}

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) if (ans[j]==1) q.push(j);
        cnt.assign(n,0); ans2.assign(n,0);
        while(!q.empty()) {
            int node = q.front(); q.pop(); 
            for(int elem: adjLRev[node]) 
                if (++cnt[elem]==adjL[elem].size()) {
                    ans2[elem]=1; 
                    if(!ans[elem]) q.push(elem);
                    // printf("ans2[%d]=1 ", elem); cout << "push: " << elem << endl;
                }
        }
        // for(int j=0; j<n; j++) printf("ans [%d]=%d ",j,ans[j]); printf("\n"); 
        // for(int j=0; j<n; j++) printf("ans2[%d]=%d ",j,ans2[j]); printf("\n\n"); 
        bool update=false;
        for(int j=0; j<n; j++) if(ans[j]&&!ans2[j]) {ans[j] = 0; update=true;}
        // printf(update? "yes\n":"no\n");
        // for(int j=0; j<n; j++) printf("ans [%d]=%d ",j,ans[j]); printf("\n"); 

        if (!update) return ans2;
    }
}
// vector<int> subtask4(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
//     // printf("subtask4\n");
//     int n=a.size(), m=u.size();
//     vector<vector<int>> adjL(n+1), adjLRev(n+1);
//     for(int i=0; i<m; i++) {adjL[u[i]].push_back(v[i]); adjLRev[v[i]].push_back(u[i]);}

//     vector<int> ans(n), cnt(n);
//     // dis(n+1), fin(n+1);
//     for(int i=0; i<n; i++) {
//         if(r[i]) {
//             // dis.assign(n+1,0);
//             // fin.assign(n+1,0);
//             cnt.assign(n,0);
//             adjLRev[n] = adjLRev[i];
//             // printf("Adjacency List\n"); printAdjList(adjL);
//             // printf("Adjacency List Reverse\n"); printAdjList(adjLRev);

//             // printf("i=%d\n",i);
//             queue<int> q; q.push(n);
//             while(!q.empty()){
//                 int node = q.front(); q.pop();
//                 // printf("node=%d\n",node);
//                 // if (node == i) {ans[i] = 1; break;}
//                 for(int elem: adjLRev[node]) { 
//                     // printf("elem=%d ",elem);
//                     if(++cnt[elem]==adjL[elem].size()) {
//                         if (elem==i) {ans[i]=1; break;}
//                         else q.push(elem);                
//                     }
//                 }
//             }
//             while(!q.empty()) q.pop();
//             // dfs4(n,i,adjL,dis,fin,ans);
//         }
//     }
//     // return ans;
//     printf("\n"); for(int i=0; i<n; i++) printf("ans[%d]=%d ",i,ans[i]); printf("\n");
//     queue<int> q; cnt.assign(n,0);
//     for(int i=0; i<n; i++) if(ans[i]) {q.push(i);} // cout << "push: " << i << endl;}
//     while(!q.empty()) {
//         int node = q.front(); q.pop(); 
//         for(int elem: adjLRev[node]) 
//             if (ans[elem]==0 && ++cnt[elem]==adjL[elem].size()) {ans[elem]=1; q.push(elem);} // cout << "push: " << elem << endl;}
//     }
//     return ans;
// }

vector<int> subtask3(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
    // printf("subtask3\n");
    int n=a.size(), m=u.size();
    vector<vector<int>> adjL(n+1), adjLRev(n);

    for(int i=0; i<m; i++) {adjL[u[i]].push_back(v[i]); adjLRev[v[i]].push_back(u[i]);}

    vector<int> ans(n), dis(n+1);
    for(int i=0; i<n; i++) {
        if(r[i]) {
            dis.assign(n+1,0);
            adjL[n] = adjL[i];
            dfs3(n,i,adjL,dis,ans);
        }
    }
    queue<int> q;
    for(int i=0; i<n; i++) if(ans[i]) q.push(i);
    while(!q.empty()) {
        int node = q.front(); q.pop(); 
        for(int elem: adjLRev[node])
            if (ans[elem]==0) {ans[elem]=1; q.push(elem);} 
    }
    return ans;
}

vector<int> subtask2(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
    int n=a.size(), m=u.size();
    // queue<int> q;
    vector<vector<int>> adjL(n), adjLRev(n), adjM(n,vector<int>(n));
    vector<int> inDeg(n), outDeg(n);

    for(int i=0; i<m; i++) {
        adjL[u[i]].push_back(v[i]); adjLRev[v[i]].push_back(u[i]);
        adjM[u[i]][v[i]] = 1;
        inDeg[v[i]]++; outDeg[u[i]]++;
    }
    for(auto& list: adjL) sort(list.begin(),list.end());
    for(auto& list: adjLRev) sort(list.begin(),list.end());

    // printf("Adjacency Matrix\n"); printAdjMatrix(adjM);
    // printf("Adjacency List\n"); printAdjList(adjL);
    // printf("Adjacency List Reverse\n"); printAdjList(adjLRev);

    // printf("outDegree\n"); printDegree(outDeg);
    // printf("inDegree\n"); printDegree(inDeg);

    vector<int> ans(n);

    for(int i=0; i<n; i++) 
        if(r[i] && !ans[i]) {
            vector<int> dis(n); int j;
            dis[i] = 1;
            if(a[i]) {
                for(j=0; j<adjL[i].size(); j++) 
                    if(dfs(adjL[i][j],i,a,r,adjL,dis,ans)) break;
                if (j<adjL[i].size()) {ans[i] = 1;} // printf("ans[%d]=%d\n",i,ans[i]);}
            }
            else {
                for(j=0; j<adjL[i].size(); j++) 
                    if(!dfs(adjL[i][j],i,a,r,adjL,dis,ans)) break;
                if (j==adjL[i].size()) {ans[i] = 1;} //  printf("ans[%d]=%d\n",i,ans[i]);}
            }
            // if (ans[i]) printf("win %d \n",i);
        }

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if (ans[j]==0) checkNeighbor(j,a,adjL,ans);
       
    return ans;
}

vector<int> subtask1(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
    int n = a.size(), m = u.size();
    vector<int> ans(n);
    vector<vector<int>> adj(n,vector<int>(n));
    for(int i=0; i<m; i++) adj[u[i]][v[i]] = 1;
    ans[n-1]=r[n-1];
    for(int i=n-2; i>=0; i--)
        if (a[i]) {ans[i] = adj[i][i] && r[i] || adj[i][i+1] && ans[i+1];}
        else {ans[i] = (adj[i][i]==0 || r[i]) && (adj[i][i+1]==0 || ans[i+1]);}
    return ans;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    return fulltask(a,r,u,v);
    if (isSubtask4(a)) return subtask4(a,r,u,v);
    if (isSubtask3(a)) return subtask3(a,r,u,v);
    if (isSubtask1(u,v)) return subtask1(a,r,u,v);

    int n = a.size(), m = u.size();
    vector<vector<int>> adj(n);

    for(int i=0; i<m; i++) adj[u[i]].push_back(v[i]);
    for(int i=0; i<n; i++) sort(adj[i].begin(),adj[i].end());


    // if (isSubtask2(n)) return subtask2(a,r,u,v);
    // for(int i=0; i<n; i++) {
    //     cout << i << ": ";
    //     for (const int elem: adj[i])
    //         cout << elem << " ";
    //     cout << endl;
    // }

}

Compilation message

train.cpp: In function 'bool isSubtask3(const std::vector<int>&)':
train.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0; i<a.size(); i++)
      |                  ~^~~~~~~~~
train.cpp: In function 'bool isSubtask4(const std::vector<int>&)':
train.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i=0; i<a.size(); i++)
      |                  ~^~~~~~~~~
train.cpp: In function 'bool dfs(int, int, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
train.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i=0; i<adjL[now].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~
train.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(i=0; i<adjL[now].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~
train.cpp:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if (i==adjL[now].size()) ans[now] = 1;
      |             ~^~~~~~~~~~~~~~~~~~
train.cpp: In function 'void checkNeighbor(int, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<int>&)':
train.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int i=0; i<adjL[now].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~
train.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(i=0; i<adjL[now].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~
train.cpp:81:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         if (i==adjL[now].size()) ans[now] = 1;
      |             ~^~~~~~~~~~~~~~~~~~
train.cpp: In function 'void dfs3(int, int, const std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
train.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=0; i<adjL[now].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> fulltask(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:129:41: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |                 if (a[elem] || cnt[elem]==adjL[elem].size()) {
train.cpp: In function 'std::vector<int> subtask4(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:163:32: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |                 if (++cnt[elem]==adjL[elem].size()) {
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> subtask2(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:279:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  279 |                 for(j=0; j<adjL[i].size(); j++)
      |                          ~^~~~~~~~~~~~~~~
train.cpp:281:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  281 |                 if (j<adjL[i].size()) {ans[i] = 1;} // printf("ans[%d]=%d\n",i,ans[i]);}
      |                     ~^~~~~~~~~~~~~~~
train.cpp:284:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  284 |                 for(j=0; j<adjL[i].size(); j++)
      |                          ~^~~~~~~~~~~~~~~
train.cpp:286:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  286 |                 if (j==adjL[i].size()) {ans[i] = 1;} //  printf("ans[%d]=%d\n",i,ans[i]);}
      |                     ~^~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> subtask1(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:305:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  305 |         if (a[i]) {ans[i] = adj[i][i] && r[i] || adj[i][i+1] && ans[i+1];}
train.cpp: In function 'std::vector<int> fulltask(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:114:33: warning: control reaches end of non-void function [-Wreturn-type]
  114 |     vector<vector<int>> adjL(n+1), adjLRev(n+1);
      |                                 ^
train.cpp: In function 'std::vector<int> subtask4(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:149:33: warning: control reaches end of non-void function [-Wreturn-type]
  149 |     vector<vector<int>> adjL(n+1), adjLRev(n+1);
      |                                 ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 6432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 1092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 419 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1592 KB Output is correct
2 Correct 8 ms 1372 KB Output is correct
3 Correct 6 ms 1368 KB Output is correct
4 Correct 7 ms 1372 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 6 ms 1400 KB Output is correct
7 Correct 6 ms 1368 KB Output is correct
8 Correct 6 ms 1496 KB Output is correct
9 Correct 6 ms 1372 KB Output is correct
10 Correct 6 ms 1552 KB Output is correct
11 Correct 9 ms 1368 KB Output is correct
12 Correct 6 ms 1372 KB Output is correct
13 Correct 6 ms 1624 KB Output is correct
14 Correct 5 ms 1368 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 1372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 6432 KB Time limit exceeded
2 Halted 0 ms 0 KB -