oj.uz

Submission #391762

# Submission time Handle Problem Language Result Execution time Memory
391762 2021-04-19T17:32:34 Z ollel Paths (BOI18_paths) C++14
23 / 100
 3000 ms 3984 KB 
#include <bits/stdc++.h>
#include <bitset>
#include <iostream>
using namespace std;

typedef vector<int> vi;
typedef long long ll;

#define rep(i,a,b) for(int i = a; i < b; i++)

int n,m,k;
vector<vi> adj;
vi clr;

const int maxN = 300300;
const int maxK = 7;

ll ans = 0;

void get(int node, bitset<maxN> &visited, bitset<maxK> &clrs) {
  ans++;
  visited.flip(node);
  clrs.flip(clr[node]);
  // rep(i,0,10) cout << visited[i] << " ";
  // cout<<endl;
  // rep(i,0,10) cout << clrs[i] << " ";
  // cout << endl;
  rep(i,0,adj[node].size()) {
    // cout << visited[adj[node][i]] << " " << clrs[clr[adj[node][i]]] << endl;
    if ((!visited[adj[node][i]]) && (!clrs[clr[adj[node][i]]])) {
      get(adj[node][i], visited, clrs);
    }
  }
  visited.flip(node);
  clrs.flip(clr[node]);
}

int main()
{
  cin>>n>>m>>k;
  adj.resize(n); clr.resize(n);
  rep(i,0,n) cin >> clr[i];
  int x,y;
  rep(i,0,m) {
    cin>>x>>y;x--;y--;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  bitset<maxN> visited(0);
  bitset<maxK> clrs(0);
  rep(i, 0, n) {
    get(i, visited, clrs);
  }
  ans-=n;
  cout<<ans<<endl;

}

Compilation message

paths.cpp: In function 'void get(int, std::bitset<300300>&, std::bitset<7>&)':
paths.cpp:9:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(i,a,b) for(int i = a; i < b; i++)
......
   28 |   rep(i,0,adj[node].size()) {
      |       ~~~~~~~~~~~~~~~~~~~~           
paths.cpp:28:3: note: in expansion of macro 'rep'
   28 |   rep(i,0,adj[node].size()) {
      |   ^~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Execution timed out 3081 ms 3984 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Execution timed out 3062 ms 1404 KB Time limit exceeded
3 Halted 0 ms 0 KB -